Pues acabo de hacer una prueba:
He activado el GPS, sin reiniciar, ni cerrar apps ni borrar nada.
He puesto el google maps y se ha conectado en menos de 10 segundos. Estoy en la Diagonal de Barcelona, en la sexta planta de un edificio de nueve y a metro y medio de la ventana.
Rom stock, con la última actualización oficial (todo por kies) y no soy root.
Por dar información y descartar...