Mmm parece que tienes algo muy puerco en android jeje. Si tenias respaldo con root restaura google play y google now, solo datos.
Si no tienes root Intenta hacer lo mismo con marco de servicios de Google, reinicia el móvil despues de hacerlo.
Si no funciona y no tenias respaldo, me temo que te queda solo restaurar de fábrica.