Para resolver o problema, abra sua pasta de configuração do Skype, geralmente é /home/{your_home_folder}/.Skype/
e exclua o arquivo shared.xml
encontrado aqui.
Depois de reiniciar o Skype, será possível fazer o login com a conta da Microsoft.