Ho avuto il tuo stesso problema... l'unico modo che ho trovato per sistemare il problema è rimettere la stock e reinstallare tutto, evitando di spegnere i servizi di play Service...
Ma a nessun altro è mai capitato? Sembra che qualche terminale abbia una gestione differente del GPS...