Pelo menos para o Ubuntu 12.04, o problema é o cache DNS local rodando em 127.0.0.1 (dnsmasq). O Webupd8.org tem um roteiro e um script para alterar o IP de escuta local para 127.0.0.2.
Desça até a seção do Ubuntu. Eu tenho que trabalhar tanto para 11,10 x64 e 12,04 x64 usando seu script. Inicialmente, não estava funcionando no 11.10, mas uma reinicialização completa resolveu isso.