There may be an example telnet entry in /etc/xinetd.conf that's commented out, if that file exists. Here is the telnet line from my Slackware install (Slackware uses ordinary inetd, but I think they're fairly similar)
# Telnet server:
#telnet stream tcp nowait root /usr/sbin/tcpd in.telnetd
If you're lucky, that file will exist and a similar line will be there. Just open the file in a text editor and remove the hash '#' from the beginning of the line:
If not, try adding that line to the file in /etc/xinetd.d/ you already created?
EDIT: Whoops, bathory beat me to it and seems to have a much better idea of what's going on. Listen to him :-)