xinetd кто нибудь настраивал?

у меня, к примеру, в /etc/xinetd.conf строки с описанием telnet имеются. с них просто комментарий убрать и все. проверь установлен ли у тебя сам пакет телнетовый. А вообще - телнету бой! переходи на ssh, оно надежней и спокойней...