A mi me pasó algo parecido y lo solucioné con un wipe data y activando en la configuración GPS las opciones EPO, aquí entras también en su configuración y descargar los datos de los satelites, y A-GPS.
No se si al resto le funciona bien sin tener que activarlos, pero en mi caso tengo que hacerlo así. Si alguno al que le funcione bien puede compartir el gps.conf, pues genial