This problem can occur when your Debian Linux system is using packages from main Debian repository as well as from http://www.debian-multimedia.org/ . For example VLC will report a following error:
main decoder error: no suitable decoder module for fourcc `XVI
What needs to be done is to remove vlc and downgrade libavcodec51 package and its dependencies. To do this you can use:
apt-get install --reinstall =0.svn<version>
or remove the package with
dpkg -P
Once done remove http://www.debian-multimedia.org/ from /etc/apt/sources.list then execute
apt-get update
and install vlc again:
apt-get install vlc