It sounds like this isn't a bug in the package (which hasn't changed since its release on 2016-03-10).
Here is the list of packages on my 16.04 system you might want to try (re)installing: gstreamer1.0-alsa gstreamer1.0-clutter-3.0 gstreamer1.0-fluendo-mp3 gstreamer1.0-libav gstreamer1.0-plugins-bad gstreamer1.0-plugins-bad-faad gstreamer1.0-plugins-bad-videoparsers gstreamer1.0-plugins-base gstreamer1.0-plugins-base-apps gstreamer1.0-plugins-good gstreamer1.0-plugins-ugly gstreamer1.0-plugins-ugly-amr gstreamer1.0-pulseaudio gstreamer1.0-tools gstreamer1.0-x libgstreamer-plugins-bad1.0-0 libgstreamer-plugins-base1.0-0 libgstreamer-plugins-good1.0-0 libgstreamer1.0-0 ** Changed in: totem (Ubuntu) Status: New => Invalid -- You received this bug notification because you are a member of Ubuntu Desktop Bugs, which is subscribed to totem in Ubuntu. https://bugs.launchpad.net/bugs/1751578 Title: Totem no longer plays MP4s, despite correct plugins installed To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/totem/+bug/1751578/+subscriptions -- desktop-bugs mailing list desktop-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/desktop-bugs