Buenas noticias.
Me he ido al recovery y he hecho:
- Wipe Dalvik-Caché
- Wipe Caché
- Fix Permissions
Y después de reiniciar (y esperar tooooodo lo que tarda), he arrancado el GPS Status y, ha tardado un poco, pero ¡por fin! ha empezado a localizar satélites (lentamente, eso sí) y me ha posicionado con 10 m de error. ¡¡¡PERFECTO!!!
Espero que al menos le valga a alguien más.