Well, I'm on VZW, with a 9530 on v126.96.36.1998, and use Google maps just fine. Resolves to a just a few meters.
When you update the OS, it backs everything up and restores it all, and perhaps it restored the problem along with everything else.
Before settling on re-upping on VZNav, I'd:
1) do a complete wipe (I use JL_Cmder
2) reinstall the OS, and
3) reinstall the apps.
A beta OS that messed me up bad left trouble for one app after reverting to .148, and doing this cleared it. PITA, for sure, but cheaper than VZNav.