Ya está todo funcionando de nuevo, han eliminado la última versión de los Servicios de Google Play y con ello el problema.
Yo tenía todo lo de Google desinstalado, he instalado de la App Store de Meizu el Google Installer, he seguido sus instrucciones y a partir de ahí el resto por Google Play, y todo funcionando sin problemas.