1. Закомментировать репозитарий debian-multimedia.org в /etc/apt/sources.list.
2. Удалить пакеты.
# aptitude remove libavcodec51 libavdevice52 libavformat52 vlc libavutil49 libpostproc51 libswscale0 ffmpeg
3. Обновить базу пакетов.
# aptitude update
4. Установить пакеты заново.
# aptitude install libavcodec51 libavdevice52 libavformat52 vlc libavutil49 libpostproc51 libswscale0 ffmpeg
5. Удалить папку настроек VLC
$ rm -fr ~/.vlc/
Вроде все должно заработать.