I'd imagine he'd have known if the server was "down" considering, well, that it was HIS server in the first place. Lets see. Skull, since you have decided to go ahead and stick to unsecure connections, which is Ok so long as you don't care about your boxes security, then if you are using RedHat 7.1 or later. Type /sbin/service xinetd start. Then try connecting. If that doesn't work. Do an ls /etc/xinetd.d/. If there is a file in there called telnet. Open it up. vi /etc/xinetd.d/telnet. Look at the file. Does it by chance say "disable = yes"? If so. Change that to "disable = no". Then try telneting. Guaranteed success. This will probably work for Mandrake and SuSE as well. The default location of the in.telnetd executable by the way is /usr/sbin/in.telnetd. Here is what my /etc/xinetd.d/telnet file looks like. Feel free to create the file if it doesn't already exist. (So long as you have an /etc/xinetd.d directory.)

Code:
service telnet
{
        flags           = REUSE
        socket_type     = stream
        wait            = no
        user            = root
        server          = /usr/sbin/in.telnetd
        log_on_failure  += USERID
        disable         = yes
}
Just put that in the directory and everything will work. Considering you change disable on over to no. Oh. Also. Do a /sbin/chkconfig --list. Make sure xinetd is listed as on in run levels 3, 4, and 5. If they aren't. Do a /sbin/chkconfig --level 345 xinetd on. If that doesn't work. Do --levels. Can't remember off the top of my head which one it is. Well. That should explain a lot maybe. Let me know. Oh yes. Another thing. To check to see whether you have the telnet server even installed. If you are using a rpm based distribution, do this rpm -qa | grep telnet-server. This should pop up a response. If you don't get anything from that. Install the damned thing. This should be it. If you need any more info, feel free to let me know.