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