/etc/xinetd.d/telnet
It defines how telnet service should be started upon connection.
Look for "disable" line and it should be set to "no".
This is "telnet" file from my REDHAT machine.
# default: on
# description: The telnet server serves telnet sessions; it uses \
# unencrypted username/password pairs for authentication.
service telnet
{
flags = REUSE
socket_type = stream
wait = no
user = root
server = /usr/*****in/in.telnetd
log_on_failure += USERID
disable = no
}