Установка плагинов

sudo apt-get install gstreamer0.8-mad
sudo apt-get install gstreamer0.8-plugins
sudo apt-get install gstreamer0.8-plugins-multiverse
sudo apt-get install gstreamer0.8-ffmpeg
sudo apt-get install vlc
sudo apt-get install totem-xine
sudo apt-get install xine-ui
sudo gst-register-0.8

Последняя строчка нужна для регистрации в системе плагинов gstreamer-а. Без нее система не будет знать, что плагины установлены.