I'm getting the same thing on an i-mate jasjam. I can access the web fine (on 3g or wireless) but Skype gets Unable to connect to internet. On the Telstra network in Australia (no doubt running Telstra firmware) if that has anything to do with it....
Michael
Ah - fixed my own problem - it was the Telstra Proxy!
From another post
CODE
had the same problem on Telstra Next-G
the solution is:
1. Go to Programs: Proxy Manager
2. select: Disable Telstra proxy manager