A mi me pasó algo parecido. Borra TODO lo de google: gmail, google fotos, play store, sin olvidarte de ninguna app, borra la cuenta de google (sincroniza si quieres antes los contactos), luego vete a la app store e instala el google installer y a partir de ahí ve instalando de nuevo todas las apps de google de nuevo. Debería funcionar