Pues seguramente lo tengas que limpiar y reinstalar las aplicaciones.
Prueba con SDMaid.
Muy posiblemente tengas que terminar limpiando manualmente si te da problemas de reinstalación para poder reinstalar las aplicaciones.
Pero una pregunta ¿Reinstalaste la Play Store sin más o descargarte las Gapps para hacerlo? Si lo hiciste sin más muy raro que te funcione, con esta y otras aplicaciones no vale el reinstalar sin más.