Eu tive problemas semelhantes uma vez, com a versão do Skype encontrada no site oficial.
Se você também baixou a sua versão lá, você pode tentar usar a versão do Skype encontrada no repositório Canonical Partner, que é otimizada para o Ubuntu (e especialmente: pulseaudio). Para obter essa versão, primeiro desinstale sua instalação atual do Skype e siga este guia: