Probablemente se deba a que no tienes definido el APN de movistar.
Vete a Ajustes -> conexiones inalámbricas-> redes móviles -> Nombres de puntos de acceso, y mira a ver si tienes uno que se llame Telefónica.
Si no es así, entonces Menu -> Nuevo APN y metes los siguientes datos:
Nombre: Telefonica
APN: telefonica.es
Proxy: 10.138.255.133
Puerto: 8080
Nombre usuario: telefonica
Contraseña: telefonica
Servidor: No definido
MMSC:
http://mms.movistar.com
Proxy de MMS: 10.138.255.5
Puerto de MMS: 8080
MCC: 214
MNC: 07
Tipo de autenticación: PAP
Tipo de APN: internet+mms
Guárdalo y reinicia el móvil.
Coméntanos si así te deja conectarte a las redes móviles.