Mmm por lo general el GPS suele tardar unos minutos (hasta 10 en los peores casos) en encontrar la señal (hablo sin la ayuda de la conexion de datos) pero a mi me ha funcionado bien en España, Portugal, y Alemania.
Aqui viene una pequeña guia, a mi me funciona pefecto, ayer mismo me cogio un satelite a los 2 segundos.
http://www.miui-au.com/howtos/faster-gps-fix
Eso sí, una vez que has hecho todos los pasos que vienen ahi, para que te coja señal rápido la proxima vez tienes que abrir el GPS status antes que el navegador.
Creo que lo que hace es descargfar la posicion de los satélites, así que incluso si estuvieras fuera de España y tuvieras que reconfigurarlo (hacer los pasos otra vez) sólo sería usar la tarifa de datos durante unos segundos.