Tinkster's right. You might want to check your inetd.conf file also which has all your services that are available to run. Make sure that your telnet service isn't commented out (doesn't have a # at the beginning of the line). I don't know where your inetd.conf is located as I don't use RedHat, but you can do a "whereis inetd.conf" or "locate inetd.conf" and that might produce better results for you. Another one to check is /etc/services which will list all your ports and the services connected to them (telnet is typically port 23). Make sure that the port isn't commented out there as well.
I do, however, have to agree with Tinkster in that you should probably look into ssh instead of telnet, but it's your system so you can do what you want. Hope this helps.