A melhor dica, como diz Michael Hampton, é não use o telnet
I open telnet client from local or remote console
Você está telnetando para a máquina local? Ou isso acontece quando você telnet fora do servidor e em? O topo da minha lista para verificar seria que a sua configuração TERM está correta e o banco de dados termcap está presente / não corrompido.