O conflito de endereço IP acabou sendo a causa raiz quando eu vi esta mensagem de erro SSH.
Depois de ler as respostas acima, suspeitei de um conflito de endereços IP, mas precisei provar que o conflito de endereços era ou não o problema.
Este artigo excelente mostrou como use arp-scan para ver se duas peças de hardware estavam reivindicando o mesmo endereço IP.
No meu caso, a máquina do servidor tinha um endereço IP estático de 192.168.1.42, eu usei arp-scan para verificar esse endereço:
$ sudo apt-get install arp-scan
$ arp-scan -I eth0 -l | grep 192.168.1.42
192.168.1.42 d4:eb:9a:f2:11:a1 (Unknown)
192.168.1.42 f4:23:a4:38:b5:76 (Unknown) (DUP: 2)
Claro que houve um conflito, como mostrado acima. Então eu corri arp-scan sem o grep, achei que .43 estava disponível, fui e editei /etc/network/interfaces
e mudei o ip estático de .42 para .43