Pues esto parece grave. Desinstalando actualizaciones de Google se soluciona para la app de Google, pero no para las apps de YouTube o Play Store. Hay usuarios que dicen que ni con un hard reset se soluciona.
Básicamente estoy sin Google, YouTube ni Play Store a no ser que esté con wifi.