What type of OS are trying to telnet too? Perhaps the inetd has been disabled on the Server you are trying to connect too. Also try to telnet to IP specific instead of hostname, if you haven't tried that already.