Eu tive o mesmo problema em 12.04 uma vez. Eu tentei o seguinte para resolver o problema.
Renomei o arquivo resolv.conf :
$ cd /etc
$ sudo mv resolv.conf resolv.conf.backup
Eu também comentei o dnsmasq do arquivo NetworkManager.conf com
$ sudo nano /etc/NetworkManager/NetworkManager.conf
colocando um "#". Acabou:
[main]
plugins=ifupdown,keyfile
#dns=dnsmasq
[ifupdown]
managed=false
Em seguida, reiniciei o serviço gerente de rede
$ sudo restart network-manager
Se isso não funcionar, eu gostaria de uma saída da nm-tool
(NetworkManager Tool) que você precisa executar.