Just used Navigation and it worked fine.
Try downloading GPS Status from the Play Store. In the app, select Tools and reset A-GPS data and re-download A-GPS data. The app also shows how many satellites your phone has locked on to.
Sent from my SGS III
I had trouble locking onto a satellite for the first time today. It reminded me of when I had my Droid X. Hopefully it was a GPS issue and not a phone issue.