From the Skyp-faqs:
------------------------------------------------
I can't connect to Skype from work or due to a restrictive firewall. Which ports need to be opened in order to use Skype?
If you aren't familiar with firewalls or ports, it may be a good idea to ask a system administrator or tech-savvy friend to help you. The minimum requirement is that Skype needs unrestricted outgoing TCP access to all destination ports above 1024 or to ports 80 and 443 (the former is better, however). If you don't allow either of those, Skype will not work reliably at all. Voice quality and some other aspects of Skype functionality will be greatly improved if you also open up outgoing UDP traffic to all ports above 1024, and allow UDP replies to come back in.
In the quest for even better voice quality, it is also advisable to open up incoming TCP and/or UDP to the specific port you see in Skype Options. This port is chosen randomly when you install Skype. In the case of firewalls, this should be easy to arrange. In some routers, however, you cannot configure incoming UDP at all (but you still can configure incoming TCP port forwarding, which you could/should do).
The randomness in port selection is to improve NAT traversal for cases where several users are behind the same NAT; if they all used same ports, many NATs would behave in a way that would reduce Skype voice quality.
Also make sure that you have the latest version installed. You can do it by clicking Check for Update in Help menu in Skype or just go to the download page where you can always download the latest version.
Skype supports authenticating HTTPS/SSL and SOCKS5 proxies.
---------------------------------------------------
A good test might be to connect a pc directly to the internet (over your line) an see if it works. It might be a provider-restriction. Test and see...