Borra la cache del movil y volver a probarlo, si no funciona sigue estos pasos.
Logueate en esta Web con la cuenta de Gmail:
http://play.google.com y comprueba el estado de tu cuenta. Si entras, ves tu dispositivo y no te funciona el Market en el movil, entonces aplica un parche llamado
Market-enabler