¿Has cambiado alguna configuración o instalado algún programa/widget para cambiar el estado de los datos?. Hay muchos widget para apagar los datos que lo que hacen es modificar los APN, si lo has apagado y luego has desinstalado el widget puede haber dejado la configuración tocada y por eso no conecta.
Comprueba en Ajustes - Conexiones inalámbricas - Redes móviles - Nombres de punto de acceso - GPRS Connection (debe estar marcada) que los datos son los siguientes (sólo para Yoigo):
APN: internet
Proxy: (no establecido) (nota: puede haber un proxy, no recuerdo el número, pero yo lo dejo en blanco)
Puerto: (no establecido) (nota: igual que proxy)
Cód. país del móvil: 214 (asumiendo que estés en España, creo que sí según tu información)
Código de red móvil: 04 (como antes)
Tipo de autenticación: ninguno
Tipo APN: internet
En principio esta configuración es la correcta. Si la que tienes es diferente (si sólo cambia el proxy y el puerto comprueba que sean los correctos o dejalos en blanco) prueba a configurar una nueva con los datos que te he puesto (los datos que no he dicho nada se dejan en no establecido).
También iría bien saber si tienes root o has cambiado la ROM si te sigue fallando para seguir buscando posibles causas.
Saludos.