|I was about to say the same thing but rather than telnet I was a port scan like NMAP or what ever.|
As for waht the issue is, if there is no firewall blocking you then the problem has to be in you I.E. Configuration. Make sure it is setup not to use a proxy unless of cource you do have aproxy server then I would do a ping from your proxy to see if you are getting through.
On last silly question. Have you tried a trace route to see where the packets are getting dropped. If it is in a NAT LAN then it will be of little help but it would at least tell you if ICMP is getting out to the internet or not. Try this from the command prompt and post the results...
If you have a static public IP do not forget to redact it.