Eu sei que esta é uma pergunta antiga, mas eu encontrei esse problema algumas vezes e descobri que a solução real não é do lado do servidor, mas está do lado do cliente e essa é a primeira coisa que surge quando Eu procurei por uma solução para o problema.
OK, o OP menciona que ele está usando a versão VPS do Ubuntu. Isso me faz suspeitar que ele está executando um servidor virtual e porque ele está tendo esse problema em particular, eu aposto que o servidor está sendo hospedado localmente. Quando eu encontrei isso no passado, é devido a um problema com as ferramentas de VM. É irritante porque você precisará reiniciar completamente o sistema operacional host, mas depois disso você deve ser bom. Você pode querer apenas desligar o VMware ou talvez apenas desconectar o teclado também funcione, mas a minha área de trabalho é inicializada muito rápido, então eu geralmente faço uma reinicialização completa.
No meu caso particular, esse problema acontece a cada vez que eu tento instalar a versão mais recente do Kubuntu usando o recurso de instalação rápida do VMware (que também falha no BTW). Isso acontece mesmo quando o servidor ao qual estou me conectando é um servidor remoto. Espero que isso ajude alguém.