Prueba a hacer lo siguiente:
Entre en programas GPS RAPIDO actualiza los datos (requiere conexion a internet), reinicia el telefono por el metodo normal (pulsa boton power y apagas, y vuelves a encender) sal a la calle, abre el TOMTOM configuras un mapa, y lo dejas 4 minutos a la espera de satelites.
Si no utilizas tomtom instala el google maps y haz lo mismo, 5 minutos en la calle.
Teoricamente al actualizar los datos con gps rapido ni tan siquiera necesitaras los 5 minutos, pero, por si los necesitara hazlo asi, en teoria, todo tu problema deberia haber desaparecido, si no, postea aqui y lo resolveremos de otra forma.