Scaricati da Google il Google play service(cerca Google play services apk o download) e installalo come una normale app. A questo punto vai in impostazioni/account e riesegui l'accesso a Google. Riavvia e hai risolto. Almeno così ho fatto io.
Secondo me c'è qualche problema nell'installazione. Vabbe, misteri.