As we all know, all of the sudden Micro$oft stopped to support old version of Skype. But new Linux version of skype client is buggy and glitchy.
I was able to make the skype work. Do the following. Open the file /usr/bin/skype in a hex editor (I used the Midnight Commander viewer) and search for the version number. In my case it was the string 18.104.22.168
Replace the string with 22.214.171.124 and save.
Run skype now and enter the credentials. Should connect just fine.