I'm having exactly the same problem with Skyrocket II
One additional comment: on google maps (without navigation) the GPS usually gets my position right when I click on the button to center the map on my current location. But when I try to use the google navigation, it stays searching for gps for ages. After it finds it the first time, I can exit navigation and re-enter with no gps lag usually. But if I turn the gps or the phone off, next time I try navigation the same gps location problem occurs.
I have tried NavFree US and also had problems, so that it does not seems as a problem with the nagivation software itself (although for some reason the map alone usually gets my position right but that may be through tower and wifi auxiliaries).
I have tried turning off the google location service as some people have suggested but it didn't changed anything.
Seriously thinking about going for the downgrade... the GPS was actually one of the main reasons for buying that phone in the first place.