Eu tenho esse problema em 11.04 e 11.10.
Tanto quanto eu posso ver, o que acontece é que o PulseAudio morre, e da próxima vez que o Skype tentar reproduzir um som (para notificar sobre uma mensagem de entrada / saída), ele bloqueia. E então não faz nada. A interface do usuário é responsiva, mas o thread em segundo plano que faz a comunicação real da rede (e reproduz sons) é interrompido e não será reiniciado.
O PulseAudio é reiniciado automaticamente, mas o Skype não é inteligente o suficiente para perceber isso e se reconectar ao PulseAudio.
A única maneira de fazê-lo funcionar é killall -9 skype e reiniciar.
A maneira mais fácil de identificar o problema é observar que o registro de data e hora de suas mensagens de saída para de avançar e sempre mostra o mesmo segundo.
Como solução alternativa, fui para a configuração do Skype e desabilitei todas as notificações de som all . Agora nunca trava. Mas sinto falta das chamadas recebidas se não estou prestando atenção às notificações visuais.