Ok, parece que encontrei o problema. Eu estou usando uma versão de 64 bits do Kubuntu e, infelizmente, o skype vem apenas em 32 bits.
Se você quiser que o skype funcione, você precisa instalar os plugins de áudio de pulso correspondentes em 32 bits:
sudo apt-get install libasound2-plugins:i386
Descobri que você precisa reiniciar para que funcione depois de instalar este pacote. Você provavelmente poderia apenas reiniciar o daemon de áudio de pulso, mas eu não tentei isso.
Acho muito estranho que o pacote deb do Skype não faça isso para você automaticamente. Eu sinto que eles deveriam colocar isso como parte de um processo de instalação automática.
EDITAR : Também relevante: link
Se você instalar o skype usando as instruções fornecidas nessa página, não deverá ter problemas com o áudio, então altamente recomendará como forma de instalar o skype.