Parece que debe ser un bug generalizado de lollipop que experimentáis los heavy users, sobre todo he leído que conduciendo se pierde la señal de forma habitual.
He leído que has usado apps para el gps, pero aporto unas por si acaso:
GPS fix, sirve para reducir el tiempo de espera al fijar una localización y es compatible con sygic y otras. También desbloquea satélites fuera de rango que pueden impedir que llegue bien la señal
GPS Status Test and Fix, para recalibrar el gps, pero esto imagino que ya lo has hecho con gps stats.
FasterGPS, sirve para seleccionar un servidor NTP más próximo a nuestra ubicación y así conectar más rápido y mantener mejor la señal.
A ver si tienes suerte, pero si esto te pasa a ti en España y a otros en el resto del mundo, pinta a problema a resolver por Google en el futuro.
Salu2!