Eu encontrei este mesmo problema com o Lubuntu 14.04 LTS.
Eu eliminei ssh com
sudo apt-get purge openssh-server
e prontamente reinstalado com
sudo apt-get install openssh-server
Eu consegui me conectar novamente com o ssh.
Se você tiver personalizado o sshd_config
(ou qualquer outro arquivo de configuração ssh), certifique-se de fazer uma cópia de segurança em um local seguro antes de limpar, porque uma limpeza remove todos os arquivos de configuração, onde não é removida.