Anche a me puzza molto di problema hardware sai...
Su internet gira voce che avvitando un po' più strette le viti del retro del telefono dell'S3 e S4 migliori di molto la connessione GPS.
Se sei alla disperata, cerca su internet "Easy Fix for Samsung Galaxy S4 GPS Issue", ma io ti sconsiglio di mettere le mani e piuttosto vai di garanzia nel negozio in cui l'hai comprato.