provavelmente sua instalação está corrompida de alguma forma. Tente desinstalar o skype por isso, deve ser o suficiente:
sudo apt-get purge skype*
ou siga esta pergunta: ( Desinstalando o Skype 4.1 da versão 12.10 ) e depois instalá-lo novamente via software center ou por
sudo apt-get update
sudo apt-get install skype
se a atualização não ajuda provavelmente o skype está faltando no seu repo, então você pode tentar adicioná-lo. O Skype está no repositório de parceiros, portanto, verifique se você tem o repositório de parceiros canônicos ativado.
Se isso não ajudar, existe uma maneira feia de instalar o pacote skype a partir do pacote .deb, baixando-o da web. Aqui estão alguns passos que podem ajudá-lo: ( Não é possível instalar o Skype através de Centro de Software 12.04 )