GPS not always working
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.