Se você, como eu, tiver o Skype instalado antes de atualizar o Ubuntu 12.10 para 13.04, desinstale-o. Vá para o Ubuntu Software Center, encontre o Skype e o Uninstall.
Adicione o repositório do Ubuntu Partners, no Ubuntu Sofware Center, Edit Software Origins, adicione o seguinte repositório:
deb http://archive.canonical.com/ubuntu/ raring partner
Feche o Sofware Center e atualize as informações do repositório em um terminal:
sudo apt-get update
Abra o Sofware Center novamente, localize e instale o Skype. Você notará que um pacote adicional chamado Indicator Support for Qt está marcado, deixe assim.