C'è l'opzione per disinstallare il Play Services?
In caso di si eseguila.
Hai aggiornato Mappe a l'ultima versione? Dovresti provare a cancellare anche i dati dell'App GPS non solo del Play Services. Se così non va, allora ripristino dati di fabbrica.
Potresti anche entrare in recovery e fare il wipe di cache e dalvik.
L'App GPS dovrebbe stare dove ci sono installate tutte le App di sistema/utente. Se la trovi e cancelli i dati bene, altrimenti se non risolvi, l'unica è il ripristino dati di fabbrica.
Ciao.