Firewall program control reset: The firewall program controls inside a firewall dictates which program(s) can access the internet or your system from the outside. When you first run Skype the firewall will usually request instructions as to whether you want to permit Skype access the internet. After that first prompt the firewall should let Skype access the internet (if you told it to allow it.)
If this mechanism is corrupted you will need to reset it by removing Skype from the approved list and then re-add Skype back.
For Windows XP SP2 firewall, you can:
Stop Skype by right-clicking on the icon at the lower right corner of your desktop within the SysTray and select “Quit Skype.”
From within the control panel, select security center -> Manage Security Settings for Windows Firewall -> Exception tab, and delete all entries you find that are associated with Skype.
Restart Skype to start the firewall recognition and approval again.
You can obtain more information from Skype's site here. On specific firewalls, check these resources: