Во-первых, telnet host 22
Во-вторых, проверяйте свои настройки. Там часом не стоит настройка "только известные хосты"?
В-третьих, нормальные админы блокируют логин под рутом. Возможно, владелец удалённого хоста наконец поумнел или завёл толкового админа?