A mi me paso eso y se soluciono de la siguiente forma.
1º borrar datos del market, no funcionó.
2º hacer los wipes de cache(no de data que borras todo), no funcionó.
3º hacer los wipes de cache otra vez y reinstalar las gapps, funcionó.
Pero como hay tanta gente a la que le falla el market estos dias igual fue casualidad.
