Ok If you have an anti virus software that blocks ports that would be one thing I would check
I would definitely try turning the firewall off just to check.
But if that didn't work I would use Revo Uninstaller Pro
Download and install this
Open the program you will see a list of all installed software
Right click on skype
It will go through 3 steps
1) Analyze and backup registry
2) remove skype
3) It will ask you to pick an option chose advance and then hit scan it will scan for all traces of skype
Once it finds all the traces select all and then delete all
Reboot your computer
Then download a fresh copy of skype and see if it works with the default settings.
Also one thing is to make sure the account you are using with skype is an administrative account just to make sure you have full rights.
If it still doesn't work after that I will opt out and allow another expert to chime in if you like