NOTA: estou recebendo notificações de comentários para o Q acima, mas parece que eles não estão sendo postados. Bug na migração da questão?
No meu caso, isso foi algum tipo de erro de roteamento ao usar um nome de domínio para ssh no servidor (que estava na Amazon). O ssh -vvv revelou que estávamos sendo roteados para outro IP por algum motivo (suspeito que o DNS interno da AWS). ssh-ing para o endereço IP direto do servidor resolveu o problema.