Instead of using google maps. Try using just the navigation that is native to the phone.

I had a gps locating issue and it cleared itself up. Sometimes a reboot is a good thing.