Samsung S4 GPE - "GPS Signal Lost" Dilemma. Considering Factory Reset. Need Backup advice I've just found this web site and I'm hoping that I can get some advice/assistance.

I have a Samsung S4 Google Play Edition phone. The GPS worked fine for close to a year. (Location setting on High Accuracy.)  However in June of last year (I think it was around the time I got the Kit Kat update), I started having a severe GPS problem. Within 90 seconds of initiating a navigation route with Google Maps, I'd get a "GPS signal lost." voice response. As I'd continue on with my trip, I'd notice the minutes to destination would click down at the appropriate rate. I'd also notice that the blue nav triangle would update every couple minutes or so and be somewhat in the vicinity of where I actually was - but the triangle would be turned in odd directions (not in the direction of traffic flow) and be several hundred yards off. And, of course, no voice commands at all. I'm guessing it had no fix on a satellite and was just determining my approximate location from cell towers. This happens every time I initate a navigation route, and for all practical purposes, the GPS is useless. However, one odd thing is that if I was on a trip more than 40-45 minutes, the GPS would get a satellite fix and it would all of a sudden start working correctly for the rest of the trip - a pinpoint-accurate blue triangle moving with traffic and the female voice commands would start. This happens everytime around the 40-45 minute mark of a trip (if the trip lasts that long). Bizarre. I have installed a GPS Status and Fix app and it confirms the unstable GPS signal (it occasionally will fix on a satellite, but then lose it). I have uninstalled Google Maps and reinstalled. Obviously a simple phone reboot doesn't fix the problem (this has been going on since June). My phone has now been upgraded to Lollipop, still same behavior. My network provider is AT&amp;T - which concerns me as other people seem to be reporting on the net that they have GPS problem with AT&amp;T. So, I'm out of things to try except a factory reset- unless someone here has any other suggestions. (I hope you do.)

That being said, I dread a factory reset (I've never done one before), but maybe it won't be so bad. I don't mind re-downloading apps and setting up my screens again. And my emails and contacts are all synced on the Google cloud. However, I really don't want to lose my SMS Hangouts trail or my call history which goes back over a year. I see that there are a few apps that claim to backup these data. But does anyone want to suggest/recommend apps and a procedure to make sure I retain as much of this as possible post factory reset? It will be much appreciated to reduce my anxiety about the process (not that the world's going to end if I lose these data).

Thanks in advance for any help. I appreciate it.
Had same problem but was able to solve by:


open back cover
take a very small phillips-head screwdriver
remove the battery, SIM Card, and Data card
tighten all screws, especially the one on the top left hand when the back is open. Reason:  Behind that screw is the GPS contact point touching the GPS antenna, and this gets loose very often.


For me this solved the problem.

Download GPS Status and Tools from Playstore and test.

Works fine now.

Even Samsung couldn't solve this over phone, but asked me to leave the phone with their service centre which will take a week to fix.