I had a similar problem for a few months. Try this: 1. In settings, go to software update and install the latest update on your phone as long as you aren't already rooted. 2. download GPS Status, the free version. 3. enable gps and then open GPS Status. Wait for it to get a fix and then open Navigation.