A mi me ha pasado alguna vez, y lo he solucionado asi:
primero haces un nandroid backup, haces un wipe, en el assistente inicial vuelves a configurar tu cuenta gmail que sincronize i tal y despues restauras el nandroid backup para dejarlo como antes, y misteriosamente vuelve a funcionar el market.
Sobretodo no olvides el nandroid backup xd ya contaras si te funciona.