Il problema è noto, ad esempio:
http://forum.ubuntu-it.org/index.php?topic=380456.0e sembrerebbe risolto con l'installazione di quel pacchetto. Nel tuo caso sembra che non riesca a trovarlo (o non esista più nei repositry ...potrebbe darsi che abbia cambiato nome

). Non so come si chiami in Ubuntu (non la uso), prova con:
sudo apt-get install ffmpeg
P.S.: Vedo che nel riportare il comando lo hai scritto con il punto finale, ovvero:
sudo apt-get install libxine1-ffmpeg,
mica lo hai impartito in questo modo? ...il punto non ci vuole...
Prova a installare il pacchetto ffmpeg nell'uno o nell'altro modo (come si chiama in Ubuntu) e facci sapere...
...io rimarrò fuori per qualche giorno quindi per un po' non potrò più risponderti, ad ogni modo riporta eventuali problemi così potrai avere risposte anche da altri e in caso negativo quando rientro vedremo qualche possibile soluzione.
Bye
