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 -- Totem can't locate codecs h.264 and mpeg4 https://bugs.launchpad.net/bugs/543157 You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs