HERES THE FIX!!
I had this very same issue, and found a resolution for it (can't remember the source now)
After taking both system updates and rebooting, it is necessary to hard reset the device. Upon the initial boot, you must leave all options checked but the following -
- Backup and Restore options (you can turn on after the initial setup is finished from options)
- there are three location options, one being new to 4.3 and what I believe to cause this - it mentions the ability for location to be grabbed when the screen is off. You must diable this option.
Finish installation, and then you will have properly working GPS.
Here's how I'm quantifying that - before when I was in the exact same boat as those in this thread, I would open GPS test, and I could see 7 or 8 sats in view, but it wouldn't lock. Or if it did, it would work for a short period of time, and then bomb out. I drove around the city for a few hours yesterday using the GPS so we're near and dear now to each other.
After doing all this - you will IMMEDIATELY see 20 sats available upon launching gps test and then almost immediately get full lock and keep it that way.
Was a pain that I had to clear everything, but now GPS is working as I would expect it, and I've not had any issues getting full lock, even in my basement.
Hope this helps!!