GPS not always working I got an issue with GPS on my Sony Xperia M phone with Android 4.3, which seems to work but only intermittently. When it works the lock is acquired quickly, but sometimes it seems that sattelite searching is not even initiated.

  
the phone is searching for sattelites / the searching doesn't seems to be initiated (click images to enlarge)

For example, above screenshots show how it looks when the phone is searching for sattelites (left), and when the searching doesn't seems to be initiated (right; notice the missing indicators from upper-left). If in the first case the lock is acquired quickly, in the second case the lock is not acquired until the GPS indicator appears on screen (sometime after minutes of waiting).

Did anybody noticed this issue? Rebooting the phone helps, but only for a while.
Even the best GPS doesn't lock on instantly. You can use "assisted GPS", or aGPS, to help get a rough fix quickly while you wait for the more accurate GPS to get a lock; this only works when you have internet access, since it uses your IP address to locate you. Go into your device's GPS settings (Settings -> Location access)

Also try clearing the data of the navigation app and installing other gps toolbox apps to see if it fixes the issue.