Yo lo que haría sería descargar del market la aplicación GPS Status.
La abres y vas a Herramientas -> Administrar el estado de A-GPS. Te sale un cuadro y pulsas Restablecer.
Vuelves a abrir Herramientas -> Administar el estado de A-GPS. En esta ocasión seleccionas descargar, para actualizar los datos XTRA del GPS.
Después de eso, te tiene que ir bastante mejor.
