The recent consensus is that Skype doesn't work well with tor and similar programs. That's what's causing the problems. Skype has automatically blocked a few massive amount of IPs running tor exit nodes. If you are experiencing the problem so far there are only two practical ways around it:

1. Disable tor (both node and client usage!). After a day or two Skype should start working again. Should the problem persist enable logging:

   
   
   

   mkdir ~/.Skype/Logs
   
   cd ~/.Skype/
   
   mv shared.xml old_shared.xml
   
   sed 's/<Lib>/<Lib>
   
       <LogLevel>3</LogLevel>/g' old_shared.xml > shared.xml
   
   

   
   
   

   Then restart Skype, wait for the error to occur. After it post your logs in ~/.Skype/Logs in the appropriate thread of the Skype forum. They will help you! They will not react.




2. Configure a proxy for use with Skype:

   
   
   
   
   

   1. Click the Skype-Icon and select Options

   
   

   2. Under Advanced, put your proxies details for Host, Port and optionally User and Password in the appropriate fields. If you don't know a good proxy already, you need to find a trustworthy list via google. I found hidemyass to be useful. Security is more important than speed!

   
   

   3. Make sure ports are forwarded to your PC (for your proxy and incoming) connections).

   
   



3. Use a VPN connection (e.g. company or university network)

Update:

Skype support does not react to inquiries into this problem anymore. I find that very disturbing. There are multiple closed threads - all labeled offtopic. Either tor is unwanted because it gets in the way of data mining or tor users are indiscriminately blocked because of the spam emanating out of the network into Skype. Both explanations are ultimately evil.