Eu tive o mesmo problema, foi o que fiz para superá-lo:
-
Remova instalações anteriores do skype:
sudo apt-get autoremove --purge skype -
Faça uma atualização geral:
sudo apt-get update && sudo apt-get upgrade -
Faça o download da versão mais recente do skype
Inicie o Skype e ele deve funcionar bem