" Google Maps showed me 3 blocks from where I actually was."
That may not be a phone problem, Google Maps is incredible--but still full of bugs. They show all addresses in Sunrise (SE Florida) as being in Sarasota, on the central west coast.
And their geocoding (which comes from NavTeq and others) is sometimes off by more than 1/2 mile. You can't be sure the GPS isn't working, unless you get the lat/lon coordinates from the GPS and compare them to the real coordinates for your location--IF you can be sure of them, because there are map datum errors and other GPS problems that can trip up the average GPS user.
FWIW.
BTW, can the update be down via a regular internet connection and computer? Or in the store? Or is AT&T really so brain-dead that it can only be done FOTA, when they complain so loudly that there's not enough bandwidth to begin with?