Ragazzi anche io avevo lo stesso problema e non riuscivo a risolvere... adesso guardando l'immagine di zanglus (che è lo stesso errore che usciva a me) mi è venuta l'illuminazione...
Sono andato a cancellare i dati dell'applicazione "Google Play Services"... e tutto funziona a meraviglia adesso!!!