Seu problema pode ser muitas coisas.
Tente usar o ping na linha de comando com estas opções:
ping google.com
Você deve receber as respostas normalmente. Então tente isto:
ping -s 1300 -M do google.com
que determinará se você está recebendo perda de pacotes. Isso detectará se você tem um problema de rede com as configurações de MTU. Eu tive isso uma vez e produziu uma variedade de efeitos.
Se o seu Ubuntu está configurado para usar um tamanho de pacote MTU (unidade máxima de transmissão) de 1500, mas o gateway do seu ISP está permitindo apenas 1000, então você vai ter perda de pacotes e problemas como você descreve.
Fica pior se você tem um firewall no seu roteador que está bloqueando os pacotes ICMP que devem notificá-lo do erro (acontece muito porque alguns sysops acham que os pacotes ICMP são ruins).
Você também pode tentar redefinir o roteador para os padrões de fábrica.