Para elaborar a resposta de Franky, este é provavelmente um problema com a configuração do /etc/nsswitch.conf.
tl; dr: Altere a linha hosts: files mdns4_minimal [NOTFOUND=return] dns mdns4 em /etc/nsswitch.conf para hosts: files dns
Existe uma linha no /etc/nsswitch.conf chamada "hosts:" que determina como o seu computador irá resolver nomes de hosts em endereços IP. (Leia mais sobre este processo aqui: link ) Esta linha é onde o problema é mais provável.
Por padrão, o Ubuntu primeiro verifica o arquivo do host para ver se o nome do host foi especificado manualmente e, em seguida, executa uma consulta Multicast mínima (isso é usado em ambientes zeroconf, a Wikipedia tem um artigo aqui link se você quiser saber mais), seguido por uma consulta de DNS regular e, finalmente, uma consulta DNS Multicast completa.
Em ambientes corporativos que não têm DNS reverso configurado corretamente (o que aparentemente é o caso com frequência), as consultas Multicast DNS causam grandes lentidões. Para corrigir o problema, você deve corrigir DNS reverso ou remover as consultas DNS Multicast da configuração. Dado que em um ambiente corporativo você provavelmente tem um servidor DNS próprio, eu recomendo apenas se livrar da opção de consulta Multicast DNS da configuração.
Consulte o link para obter mais informações sobre esse problema.