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.