Pode haver algumas coisas.
Primeiro, o Ubuntu pode estar tentando falar sobre o IPv6. Normalmente, isso não é um problema, mas pode acontecer se seu equipamento de rede for antigo, configurado incorretamente ou apenas inferior. Uma rápida pesquisa no Google revela como fazer isso .
Se o IPv6 não é o problema, você pode tentar alterar os servidores de nomes. Vá para o aplicativo chamado Network Connections e edite sua conexão. De lá, vá para a guia IPv4 e escolha "Somente endereços automáticos (DHCP)". Insira os nameservers públicos e gratuitos do Google :