Também estava com o mesmo problema e resolvi da seguinte maneira:
1) Remova o skype intalado em seu Ubuntu. No meu caso foi:
sudo apt-get remove skype
2) Entre no site do skype (
www.skype.com)
Mas especificamente em:
http://www.skype.com/intl/pt/download/skype/linux/3) Nesta página baixe o arquivo (skype-1.3.0.53-generic.tar.bz2)
Que esta no link:
"Dynamic binary tar.bz2"4) Abra o terminal.
5) Procure o local onde o arquivo tar.bz2 foi salvo
6) Especifique o comando a seguir: "tar xjvf skype-version.tar.bz2", em que skype-version.tar.bz2 é o nome do arquivo baixado, como skype-0_90_0_1.tar.bz2. A seguir, o Skype é colocado no diretório atual. Observe que isso não exige privilégios de raiz.
-----------------------------------------------------------------------------------------------------------------------
Obs.: a) Exige Qt 3.2
b) Os passos 4, 5 e 6 foram retirados do proprio site do skype
-----------------------------------------------------------------------------------------------------------------------
Espero ter ajudado.