перешел на ленни, у меня случилось тоже самое. У меня проблема была скорее всего в том что vlc скомпилирован без поддержки ffmpeg. Попробуйте
vlc --list | grep ffmpeg
если нет - дела плохи
Я решил вопрос так:
1) скачал отсюда исходник vlc 0.9.1
http://www.videolan.org/vlc/download-sources.html
2) распаковал
3) sudo apt-get build-dep vlc
sudo apt-get install libavutil-dev libavformat-dev libmad0-dev
sudo mkdir /usr/lib/live
sudo chmod 0755 /usr/lib/live/
4) собственно перешел в папку с исходниками и скомпилировал
./configure --prefix=/home/darion/bin/vlc/ --enable-x11 --enable-xvideo --enable-gtk --enable-sdl --enable-ffmpeg --with-ffmpeg-mp3lame --enable-mad --enable-libdvbpsi --enable-a52 --enable-dca --enable-libmpeg2 --enable-dvdnav --enable-faad --enable-vorbis --enable-ogg --enable-theora --enable-faac --enable-mkv --enable-freetype --enable-fribidi --enable-speex --enable-flac --enable-livedotcom --with-livedotcom-tree=/usr/lib/live --enable-caca --enable-skins --disable-skins2 --enable-alsa --disable-kde --disable-qt --enable-qt4 --enable-wxwindows --enable-ncurses --enable-release
вместо /home/darion/bin/vlc/ выставте свои.
qt4-dev должны быть установлены.
5) make
6) make install
в итоге получился красивый (тк на 4ых qt) и удобный vlc 0.9.1 , который спокойно читает все файлы.