Have you got Telnet-server installed on this box? This webpage that I just went through suggests..
http://www.unixguide.net/linux/notes01.shtml
By default the RH Linux server does not install the telnet-server package.When you telnet to it, you are connecting to the kerberized rlogin server.If you don't want to configure a kerberos domain and just want to install the plain telnet server, just install the telnet server package off the Linux CD/DVD and try connecting again.
SSH connections will work probably because the ssh-server package is installed by default.Ideally do not use telnet at all.SSH is a mmuch better alternative.
Cheers
Arvind
p.s....Post back if the problem is still not resolved...