Prueba con el gps status a buscar los satétlites al aire libre, a ver si así consigues que rule.
Si lo consigues una vez, lo normal es luego funcione siempre...cuesta más la primera vez....es importante que lo hagas en el exterior y en un día sin nubes.
Entiendo que has entrado en ajustes/servicios de ubicación/acceder a mi ubicación (activado) /fuentes de ubicación/satelites gps (activado) y servicio de ubic de google activado
Para que no haya dudas cuando lo hagas desconecta el wifi y el 3g, ten solo activado el gps.
Prueba y nos vas contando