Samsung Galaxy S3 — Ayuda cuenta Gmail

Hola chicos
Acabo de comprarme un S3 cuando intento acceder a google play, obviamente me pide mi cuenta de Gmail, la meto y tras verificar unos segundos, se corta la verificacion con un mensaje " Error al iniciar sesion" No se puede establcer una conexion fiable con el servidor.

Es posible que se trate de un error temporal o que el dispositivo Android no esté preparado para servcios de datos. Si el problema persiste. llama al servicio de atencion al cliente.

He prodado en muchas ocasiones y nunca lo verifica, ni por wifi ni por 3G.
Tampoco me deja crear una cuenta nueva de Gmail.

Buscando en la red he visto las siguientes opciones:
Modifica la fecha,borrar los datos del google play, borrar la chaché de las cuentas de google, resetearlo, probar a acceder sin la tarjeta sim.

Tengo instalado el super usuario pero no puedo instalar ninguna aplicacion hasta que no acceda a google play.
¿Alguien puede ayudarme?

Muchas gracias