Atualizei meu Ubuntu 13.04 para o 13.10, o que acredito que faça com que o Skype não funcione corretamente.
Por exemplo, em 13.04 estava funcionando OK, ele ainda está trabalhando no Windows 8 (então não há nada errado com minha conexão com a Internet), mas recebo a seguinte mensagem toda vez que tento enviar uma mensagem:
Ao passar o sinal eu recebo "A mensagem não é enviada". Este deve ser o caso se eu não tiver conexão com a Internet ou se a pessoa para quem estou enviando a mensagem não tiver recebido. Mas este não é o caso ...
Consegui corrigir o problema usando o link @payorivero me deu.
O problema parece ser causado pela instalação incorreta do Skype (baixei o Skype de seu site oficial).
A linha a seguir corrige o problema permanentemente:
sudo sed -i 's/^Exec=.*/Exec=env PULSE_LATENCY_MSEC=30 skype %U/' /usr/share/applications/skype.desktop
O código acima está mostrando como instalar o Skype corretamente no Ubuntu 13.10:
sudo apt-get update
sudo apt-get install skype