Yo también tengo la versión genérica de UK y cuando restauro los valores de fábrica me da la opción de sincronizar la cuenta de google desde el principio.
La verdad es que es un poco raro ese mensaje. ¿Podría ser que tengas activada la sincronización automática de los contactos, etc. y que no tengas la conexión de datos activa? Échale un vistazo a Ajustes/Sincronización de datos y prueba a actualizarlo manualmente pinchando sobre cada opción.
Intenta borrar los datos de la cuenta e introdúcelos nuevamente o prueba con otra cuenta nueva. Para ello, te transcribo lo que el compañero mhut ha aconsejado en otro hilo:
Para tu problema en concreto, solo se ocurre una cosa por ahora: Ve a Ajustes / Aplicaciones y abre "Adminstrar Aplicaciones". Espera a que cargue el listado completo y busca "Google Apps". Pulsa ahí y te saldrá información, junto a varios botones. Pulsa el que pone "Borrar datos", con lo que borrarás la cuenta que has introducido. A continuación pulsa el botón de volver y busca "Market", lo abres y si están accesibles los botones "Borrar datos" o "Borrar caché", los pulsas (si no están habilitados, salen como en gris y no deja pulsarlos).
Cuando vuelvas al market, te pedirá de nuevo que introduzcas tus datos. Ponlos de nuevo y haz la prueba a ver qué sucede.
Saludos.