Prueba FasterGPS y despues GPS Status. son apps del market y son gratuitas.
La primera la abres y te vas donde pone Continente, eliges Europa, supongo, Región España, tras esto te descargará un servidor.
Después, el GPS Status lo abres, vas a ajustes, yo lo abro con el boton de las tres rayas del móvil, vas a herramientas, y hay Administrar el estado del A-GPS. y ahí tu mismo, puedes restablecer para borrar los datos y arrancar de cero o descargar la ayuda de Internet.
Prueba a ver que tal te va.