¿Has probado a desinstalar actualizaciones del Google Play?
Ajustes -> Aplicaciones -> Administrar aplicaciones -> Google Play Store. Pulsar desinstalar actualizaciones.
Reiniciar el teléfono y ejecutar el market, dejar que se actualice de nuevo.
Si ya has probado eso y no te ha funcionado, también puede probar esto:
Reinicia el teléfono en modo Recovery.
Vete a Advanced, y ahí vete a Fix Permisions y ejecútalo (probablemente tarde un poquito).
Reinicia el teléfono normalmente y prueba de nuevo.
Si nada de esto funciona, queda el método drástico, que sería flashear desde cero...