The warning can be fixed by removing qt-at-spi from your system, then logging out and back in. I don't think it's related to the issue though.
One of the good things about mint is that it comes with the codecs you need by default, but even so it looks to me like a problem with libavcodec.
You should wait for someone more knowledgeable in the area. The best advice I can give is to (re?)install libavcodec53 and 54, maybe upgrade vlc (since they're up to 2.0.5)
PC: LMDE x64 MATE/Cinnamon, Kernel 3.9, Nvidia GT620, i7 3770K, 16GB RAM
Laptop: LMDE x64 MATE, Kernel 3.8.6, i3, 6GB RAM