Prueba en Ajustes->Aplicaciones->Administrar aplicaciones buscas el market y das a borrar datos.
Perderas todos los enlaces a de las aplicaciones instaladas al market pero acaba reaciendolos, sino con las ultimas versiones del titanium backup lo soluciono en ajustes del titanium en Mas y Market doctor.