A mi me pasaba lo mismo y encontré el fallo.
La cosa es que de un tiempo hasta ahora, estan actualizando sin avisar el market, y a mucha gente le da ese error (a mi también).
Lo que hice yo fue desactualizar el market desde administrar aplicaciones.
Ajustes --> Administrar aplicaciones --> Market --> Desinstalar actualizaciones
A mi, haciendo esto ya me funcionó. Prueba a ver si se te soluciona.
