Is your telnet service started? You may have it stopped, or not even suppoed to start for that runlevel.
But, I would personally forget about telnet and use ssh instead. SSH is similar to telnet but much more reliable and secure. I forget the default status for sshd, but a /sbin/service sshd start will enable the service if it is not started. Almost all *NIX setups have ssh clients installed (RH does). For winders puTTY can be quickly located from a google search and is great for connecting from winders to an y sshd server.