Eu tive o mesmo problema:
pst007x@pst007x-Serval-Professional:~$ dpkg -l skype*
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name Version Architecture Description
+++-==============-============-============-=================================
ii skype 4.1.0.20.0-0 amd64 client for Skype VOIP and instant
ii skype-bin 4.1.0.20.0-0 i386 client for Skype VOIP and instant
un skype-common <none> (no description available)
un skype-mid <none> (no description available)
un skype4pidgin <none> (no description available)
pst007x@pst007x-Serval-Professional:~$
Eu não pude iniciar a partir do ícone na barra Unity após a instalação, mas poderia iniciá-lo no terminal ... Eu recriou o iniciador do Skype, usando um editor de menu, e tudo funcionou bem depois disso .... apenas um estranho falha ...: - /