Comment 10 for bug 543157

I tried the solution 'vanchuck' provided, but the libavcodec52 package wasn't installed on my system. So I tried 'Sergey K' his solution and this worked out (although I didn't installed some of the packages, but better safe than sorry). Now totem did find and installed the plugin.

What I did was:
$ sudo apt-get remove gstreamer0.10-plugins-bad-multiverse mencoder libavcodec-extra-52 gstreamer0.10-ffmpeg vlc-nox videotrans libavformat-extra-52 ffmpeg libavfilter0 qdvdauthor-common qdvdauthor smplayer vlc mjpegtools libmjpegtools-1.9 vlc-plugin-pulse libquicktime1 mplayer-nogui libavdevice52 libxvidcore4 gstreamer0.10-plugins-ugly twolame gstreamer0.10-plugins-ugly-multiverse gstreamer0.10-plugins-bad

$ sudo apt-get purge libtwolame0 libmp4v2-0 libdvbpsi5 libx264-85 libmad0 libmpcdec3 libmpeg2-4 libfaac0 libfaad2

BTW: Bug #350772 seems related: https://bugs.launchpad.net/ubuntu/+source/totem/+bug/350772