A mi me funcionó lo siguiente (básicamente una reinstalación):
-desinstala play store con titanium backup o alguna otra app
-saca el apk del playstore del zip de apocalypse, colocalo en system/app de tu móvil, dale permisos rw-r-r. Reinicia.
-abre el playstore y prueba. Espera q se actualice. Te quedará una app adicional en la memoria interna del playstore.
-con titanium backup, lotes, integrar, integrar actualizaciones de app del sistema. Seleccionas el playstore y cuando acabe reinicias.
Ya debes de poder usarlo sin problemas. Suerte.