Sempre tive uma ótima conexão com os DNS fornecido pelo velox/provedor Oi, mas de uns tempos para cá tudo passou a ficar muito lento no Ubuntu inclusive não conseguia usar o Gmail, mas no Windows normal, então mudei no Ubuntu o DNS para o do Google e tudo voltou ao normal.
Agora eu mudei no NetworkManager e não diretamente no arquivo /etc/resolv.conf como foi indicado aqui, até por que ele sempre vai sobrescrever o que você colocar neste arquivo se sua conexão estiver configurada para receber o DNS do provedor e não no manual, então pode ser que a dica de alterar o DNS funcione desde que que vc desative a opção do automático, ficando no manual o fornecimento do DNS e o melhor caminho é pelo ícone do gerenciador de redes NetworkManager no canto superior direito próximo ao relógio.