Se tanto o ssh quanto o telnet apresentarem os mesmos sintomas (ou seja, ficar parado aparentemente sem fazer nada), então, com toda a probabilidade, não será um problema com a instalação do ssh.
Você verificou sua configuração de roteador / firewall? Se você não controla o roteador / firewall, fale com a pessoa que o faz. Eles podem ter mudado de política ou redigido uma reconfiguração. Eu tenho visto problemas similares com switches de commodities também, então se você tiver um switch cheapo entre sua caixa e o 'Net, tente reiniciá-lo.