Dos ultimas cosas, realiza lo que menciona el colega Bundy arriba, borra cuenta de Google, cache, datos de Servicios de Google Play, de la Play store, wipe cache y dalvick desde recovery.
Si sospechas que es la Play Store desde la app Lucky Patcher puedes instalar o reinstalarla, apartado Toolbox--Install Modded Google Play Store, seleccionas la versión de Play Store que gustes.