A função "aptitude" no terminal do Ubuntu instala qualquer aplicativo que você diga a ela junto com todas as dependências necessárias.
Se você ainda não tem o "aptitude" instalado, use "sudo apt-get install aptitude".
E então use "sudo aptitude install pitivi".
Pelo menos para mim, eu preciso de "gstreamer0.10-gnonlin" junto com o PiTiVi para fazê-lo funcionar (pode ser mais para você porque eu já poderia ter outras dependências satisfeitas).