We had this problem at work recently, and we found a few workarounds :
Fix 1
Close Skype
In a terminal, type :
rm -rf ~/.Skype
(this removes your whole Skype config, so be sure you know your login and password)
relaunch Skype
Fix 2
In a Skype chat window, type :
/dumpmsnp
If the output is :
System: MSNP: Connection Data:
* Status: LoggedOut
Then type :
/msnp24
And restart Skype.
The dumpmsnp command output should look like this :
SNP: Connection Data (MSNP24):
* Status: LoggedIn
* Server Current: XXXXXXXXXXX.gateway.messenger.live.com
* Server Saved: s.gateway.messenger.live.com
* Login: (UIC)
* Skypename: xxxxxxxxxxxxxxx
* EPID:
* ClientVersion:
* OSVersion:
* B:
* Time: TZ:
* Last Connect:
* Push: None (Unregistered)
Fix 3
Close Skype
In a terminal, type :
grep Home ~/.Skype/*/config.xml
The output should be similar to :
<HomeServer>s.gateway.messenger.live.com</HomeServer>
If this line is present but with another server, try replacing it with this server and relaunch Skype
If this line is missing, edit the config.xml file with your favorite text editor, and look for a section.
Add it, or replace it if it's already here, with this :
<MSNPCore>
<HomeServer>s.gateway.messenger.live.com</HomeServer>
<NewThreadAllowed>1</NewThreadAllowed>
<P2PMigrationAllowed>0</P2PMigrationAllowed>
<ProtocolToUse>24</ProtocolToUse>
<RecentConnectionInfo></RecentConnectionInfo>
<RecentConversationsSyncState></RecentConversationsSyncState>
</MSNPCore>