Tente o seguinte:
Configure o arquivo /etc/inetd.conf manualmente adicionando a linha "telnet stream tcp nowait telnetd /usr/sbin/tcpd/usr/sbin/in.telnetd" para ele com permissões elevadas.
Em seguida, configure o arquivo /etc/xinetd.conf manualmente adicionando
"instances = 60
log_type = SYSLOG authpriv
log_on_success = HOST PID
log_on_failure = HOST
cps = 25 30 "
para a seção de configurações padrão (com permissões elevadas).
Reinicie o Ubuntu.
Reinicie o servidor de telnet executando o comando "sudo /etc/init.d/xinetd restart".
Ao terminar, use o comando "telnet -tln" para verificar se o servidor de telnet abriu com sucesso um soquete para você na porta 23
Nesse caso, você deverá ver uma linha na saída que se parece com a seguinte:
TCP 0 0 (seu endereço local): 23 0.0.0.0:* LISTENING
Se sim, execute o ifconfig para pegar o IPv4 e levá-lo para sua outra máquina (executando o cliente telnet). Nesse terminal execute "telnet (o IPv4 que você anotou)". Se tudo estiver configurado corretamente (pode levar alguns segundos dependendo da velocidade da sua conexão), ele deve se conectar e solicitar um nome de usuário / senha. Entre e você está dentro.