I have the same problem. I downloaded Skype 4 today now can't connect. The only message that comes up says 'can't connect'. I've not had a problem with skype until now. What's going on - anyone know?
if you are sure about the FIREWALL,PROXY SETTING, and also you restarted your router you must follow these steps,
...uninstall skype ...delete skype folder in application data(you must check show hidden files in folder option then go to document and setting/your user/application data/skype)
...go to registery(type regedit in start/run)
...FIND "skype" in keys,values,data and delete all of them(you can use f3 button for next and delet boton to do it as fast as possible)
...instal new version of skype(recommended) and JOIN IT
This is may be because your firewall is blocking skype connections!
Go to Control Panel then open Windows Firewall, Just click on the exception tab and try to see if you can locate skype there! If not browse to add skype.exe in the exception list!
just stop ur antivirus program and try .. u will login >> try to tell ur antivirus to trust skepe program >> am using nod32 and it block my skype until I change my antivirus properties .. its the only problem so stop search ..