Hola,
Después de hacer varias pruebas, el problema está en la activación de los datos 3G. Debe haber algún problema con el módulo de radio que a veces se pelean el GPS y el 3G.
Cuando os pase eso (que el GPS se apaga), desactivad los datos 3G, y ya veréis como el GPS funciona bien.
Cuando el GPS esté enganchado, podéis volver a encender la activación de datos. En principio, no debería volver a fallar si no apagáis el teléfono.
Un saludo,