Hi,
On redhat 7.x, its much more likely to be because of the firewall they provide which seems to turn itself on by default. Its called lokkit and generates ipchains rules that are read by the ipchains service. Unless you know it isn't that, the first thing to do is administer that firewall to allow the telnet service through, i.e. permit inbound TCP port 23 . You do that as root with :
# /usr/sbin/lokkit
or
# /usr/sbin/gnome-lokkit (Alan Cox gnome gui version !)
If you are on a lan and want to run various services on the linux box it is maybe easiest to take the option to treat your lan interface (eth0 ?) as 'trusted' - then most stuff will be allowed through. Otherwise, just allow inbound port 23.
Restart the network :
# /etc/rc.d/init.d/network restart
... and try again. Out of the box, you should be able to login via telnet with any 'regular' linux account - but not root. Thats restricted for security purposes.
You probably read it before, but its really much more secure to use ssh instead of telnet. You need to install all the rpms on the redhat CD beginning with 'openssh' :
# mount /dev/cdrom
# rpm -Uvh /mnt/cdrom/Redhat/RPMS/openssh*.rpm
Again, you'd need to allow it through lokkit (port 22) this time. If you need a client for ssh (or even a better windows telnet client) then try PuTTY -->
Hope this helps