When I got the phone it would lock on to *at least* 10 out of 20+ satellites within seconds and maintain high accuracy. Over time, it's taken longer and longer to lock, uses fewer and fewer birds when it does (I'm lucky to see 6/12 most times), and loses position more easily.
I do an AGPS refresh regularly, tried it with several different app (my main one is GPS Status Unlocked), but it doesn't help. I recently received the OTA update to Kit Kat, but it made no difference either way.
Just fired up GPS Status and it shows 0/18 satellites... trying and trying but that's it. Meanwhile, just started GPS Status on my wife's Galaxy Tab 10.1, and it instantly shows 16/16. (Ooooh, and now the G2 is at 1/16).
I thought maybe the Otterbox was affecting reception but removing it makes zero difference as well.