Isso soa como um problema de firewall para mim. Tente usar ssh com o sinalizador -v para depurar a saída. Isso lhe dará uma pista melhor sobre qual pode ser o problema. Também tente telnet para o seu servidor ssh na porta 22 assim:
telnet yourserver 22
Você deve receber uma resposta com o número da versão do ssh.