micp, you're running into the same problem I have with the GPS about once a week, and I don't use Navigation much. The GPS will totally flakeball out on where the sats are supposed to be. It'll sync to one, which should be able to give it all the data it needs to find every other sat, but no, it sits there.
Power off, restart, open GPS Status (free app from market), blam, 15 birds in 3 seconds.
Interesting to know that WeatherBug has been tagged as interfering with the GPS. I may have to bop them on the head.
BTW, a relatively unimportant side note is that Google Navigation is currently still in Beta. Google's disclaimers are pretty clear that we should not yet rely on the app for navigation, it outright says it can send you the wrong way down a one way street. Still, the GPS and its drivers are not in beta and you're not complaining about the quality of directions.