I have some irregularities sometimes in connection to my gps also, normally fixed by restarting the map/drive app but your problem seems much worse. Have you tried any other gps-dependent apps like 4squick etc.?