It is quite obvious to me that Skype is under some form of Attack the service just would not work one minutes and not the next. They are being quite secretive about what the issue is.
They say they the issue is from some code or algorithm but I bet someone found a big hole and has crippled the service with a denial of service attack.
Not having Skype going on two days shows how much I depend on it working. Skype