What version of RedHat are you running? If you happen to be running the latest (version 9) logged in as root you can open up redhat-config-services (need to be in X-windows, graphical screen aka Gnome
or KDE or somethin)
Look down the list and check if you enabled the ssh or telnetd service. If their not enabled check either one (depending on your needs, ssh is more secure than telnet so I wouldn't enable (telnet) if I were you) and click the Start button. Then I would select the File>Save so that don't have to mess with it again.
If they are both checked and running it might be network problems. Say if your behind a router (running like Linksys) you'll need to open up a port. Now that is beyond this post so you'll have to check your manuals or ask your sysadmin to open up the port for ya. This can also be the case if your running some sort of firewall.
Telnet port is 25
SSH port is 22
If you need anymore help feel free to ask!