Gen, el tema es que la configuración automática que me había hecho el dispositivo cuando puse la SIM sobre Movistar, era la configuración de Movistar emocion... Al parecer esa conexión utiliza un proxy y eso era lo que me estaba fallando.
Ahora ya está resuelto... De todos modos muchas gracias por la ayuda y por la celeridad con la que me has respondido.
Un saludo y espero poder ayudar yo en otra ocasión.