De link
Acabei de passar a maior parte do dia conseguindo o Compartilhamento de Conexão com a Internet através do Network Manager para trabalhar no Maya. O problema é que minha instalação não tinha um /etc/resolv.conf. Se você está se conectando via DHCP, você não precisa de um, mas, aparentemente, o Compartilhamento de Conexão com a Internet do Network Manager faz.
Então faça "sudo gedit /etc/resolv.conf" e (suponha que você tenha um arquivo em branco) entre neste, substituindo os itens entre colchetes, é claro:
domain [YourDomain]
nameserver [YourPrimaryNameserver]
nameserver [YourSecondaryNameserver]
Você pode obter os IPs primários e secundários do servidor de nomes clicando com o botão direito do mouse em Network Manager e selecionando "Connection Information" e certificando-se de estar na guia do seu dispositivo de rede conectado à Internet.
Assim que eu fiz o meu resolv.conf e reiniciei, o dispositivo que eu estava compartilhando encontrou a Internet sem nenhum problema.