чтоб проверить что у тебя действительео поднят sshd коннекться telnet на 22 порт, если там слушает sshd, то в ответ он(telnet) тебе распечатает конфигурацию sshd с поддерживаемой шифрацией, если настройки все прочие верны на 100%, то попробуй приконнектится локально используя lo (127.0.0.1), включай трассировку, например:
ssh -v 127.0.0.1 -p 22
, если соединение установит, то скорее всего у тебя sshd работает через tcpwrappers, который и не позволяет соединяться с др. ипшников, чтобы разрешить это дело, заходи в /etc/hosts.allow и пиши туда адреса с которых разрешен вход по ssh. УДАЧИ!!! :-)