Eu tive esse problema 5 dias atrás depois de reinstalar o Ubuntu 13.10 64 bit. O problema é que o Skype é um programa multi-arch, então se eu não estiver errado, ele usa uma mistura de bibliotecas de 32 e 64 bits. Para resolver o problema de som acabei de instalar o pacote libpulse0: i386
sudo apt-get install libpulse0:i386
em seguida, reinicialize e o áudio por pulso apareceu em configurações de áudio no skype.