Eu tive o mesmo problema. Com o Ubuntu 12.10, eu instalei o Cisco AnyConnect e descobri que havia perdido minha conexão com a Internet. Desinstalei o AnyConnect e vi que ainda estava com problemas de DNS, o que me impedia de acessar qualquer coisa na Internet. Com base na resposta do jdthood, eu olhei para o arquivo /etc/resolv.conf e vi isso:
# Dynamic resolv.conf(5) file for glibc resolver(3) generated by resolvconf(8)
# DO NOT EDIT THIS FILE BY HAND -- YOUR CHANGES WILL BE OVERWRITTEN
nameserver 127.0.0.1
127 é um localhost ou algo assim, de modo que não parece certo. Eu comentei a última linha e adicionei isto:
nameserver 8.8.8.8
8.8.8.8
é o endereço IP do servidor DNS do Google. Isso resolveu o problema instantaneamente. Eu não tenho certeza se é uma correção permanente (a julgar pelo aviso all-caps para não fazer o que eu fiz), mas é válido após a reinicialização, e minha internet funciona novamente.