Encontrou uma solução aqui: link
O MTU do meu roteador foi configurado para 1500. Depois de alterar o MTU para 1476, tudo ficou ótimo novamente.
Então, ontem tudo estava funcionando muito bem. Meu Ubuntu 14.04 foi atualizado com a atualização linux-image-extra-3.13.0-85.129.
Quando eu inicio o computador esta manhã, notei que não posso mais SSH para meu repositório Bitbucket, o MySQL Workbench não pode se conectar a servidores remotos e até mesmo navegadores estão me dando Request Timeout ao se conectar a HTTPS. p>
Eu removi e reinstalei o openssh-server e ainda assim não tive sorte. Não tenho certeza onde procurar. Alguma idéia?