Tente baixar o Skype 4.1 .deb ,e reinstalar pela Central de Programas
http://www.skype.com/intl/pt-br/get-skype/on-your-computer/linux/depois de Instalado se não abrir :
1 procure o terminal
2 digite sudo su
3 digite sua senha de root ,e tecle Enter
4 digite skype no terminal ele deverá abrir
OBS: depois de tudo certo , e o audio do MIC não funcionar vc tem que instalar puse audio , abrir o puse audio ,e ajustes.
Caso funcione é diretório errado. Terá que edita-lo
Caso não funcione terá que remove-lo , como citou o Amigo acima .
ou tenta sudo apt-get remove skype.
T+.