Ok, isso acabou sendo WTF LOL ao quadrado ...
Eu tenho uma dica de que era mais provável pacotes ICMP sendo filtrados pelo firewall. Então, quando você se deparar com essa questão, confira.
No artigo que encontrei em Hacker News , lê-se:
ssh did not work. It would connect, flip some data back and forth (as shown with -v) and then would hang.
Certain websites would become inaccessible.
Quais foram meus sintomas que apareceram depois de mudar meu roteador sem fio para outro dispositivo. O dispositivo em questão era o Linksys WRT-54G rodando dd-wrt.