Есть только что установленный сервер в штатах. При попытке подключения по сервер ssh отдает то один, то другой ключ. Если отдает первый ключ, то дает залогинится, если другой то нет и выводится сообщение WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
Дополнение 2. Запустил tcpdump на сервере. Когда приходит ответ с OpenSSH5.3, то на серваке никакие пакеты не приходят(в tcpdump пусто).
Проблему у хостера с маршрутами?