Tengo entendido que si pasas mucho tiempo sin usar el gps pasa eso. Cada vez que te conectas y pilla gps te guarda como si dijéramos la ultima posicion y si inicias el gps en esa zona no tarda casi nada.
En cambio si usas el gps en galicia y al dia siguiente en malaga. Te tardara mucho en pillar señal xq no tiene pre guardada esa zona. Lo mismo si no lo enciendes en mucho tiempo.
Yo en una htc que tenia te daba la opcion de gps rapido. Se conectaba a internet y descargaba un fichero y no tardaba nada en pillar señal. Creo que en el market tambien hay app para eso.