Recentemente chegaram 2 aparelhos motorola (Um moto G-xt1033 e um moto E-xt1025) em minha assistência, ambos com o mesmo problema. Ao tentar fazer login na Play Store, logo depois de digitar a senha, ocorria um erro (Google Play Services parou).
Os dois aparelhos rodavam Android 5.1 e mesmo reinstalando a ROM o problema permaneceu.
Só consegui solucionar desbloqueando o bootloader para conseguir fazer downgrade e posteriormente atualizar via OTA (os aparelhos tem uma proteção e com o bootloader bloqueado, ele impede a gravação de uma ROM mais antiga que a ja instalada).
Aparentemente é um problema com a ROM 5.1 e acredito que vem acontecendo em outras marcas também (http://www.clangsm.com.br/topic/109443-sony-t2-google-parou/?_fromLogin=1)
Talvez seja um problema temporário, mas fica aqui a dica pra quem não está conseguindo resolver.
E se alguém souber uma maneira mais fácil de solucionar, agradeço.