Não importa, acabei de encontrar a solução.
Existe uma pegadinha no Ubuntu 12.04.
Para que isso funcione, vá para Configurações IPv4 e altere Method
para: Automatic (VPN) addresses only
. Depois disso, vá para DNS servers
e digite o endereço do seu servidor DNS favorito. Eu gosto do OpenDNS, então os endereços serão: 208.67.222.222, 208.67.220.220.