telnet is a very generic program, able to connect via tcp to any port. Traditional "telnet" runs on a specific port - port 23. Telnet should work. Your ISP may have blocked port 23, but telnetting to another port will work.
To prove my point try "telnet www.macosx.com 80", this will connect...