Esta notícia que acabei e ler no Tecnoblog vai agradar usuários do Skype no Linux (Skype para Linux chega à versão 4.0 com nova janela de bate-papo | Tecnoblog). Já hé pacotes prontos para Ubuntu, Debian, Fedora e OpenSuse e o download pode ser feito diretamente o site do programa.
Já me antecipando a possíveis questionamentos, caso você instale no Ubuntu 12.04 64bits e ele não inicie, instale o pacote ia32-libs e exclua o arquivo .Skype/shared.xml e .Skype/shared.lck no seu home. Feito isso o Skype deverá iniciar sem problemas com áudio e vídeo.