Can you browse websites with Internet Explorer, even if it's not your primary browser?
If IE connects to websites normally, try clearning the Browsing history (cache) in IE via IE > Internet Options. Then, in IE Options > Advanced click on the Reset button to restore IE to factory default settings.
See if those steps let Skype connect.
Please note: I do not respond to requests for help via Private Message.