Well, I'm making some progress finding things out.
On my Ubuntu system it's gstreamer-plugins-ffmpeg that enables watching movies (at least the avi, not sure about the mpeg). In a virtual Gentoo I could reproduce that, but in the virtual Fedora movies still don't play.
On the Ubuntu it's gstreamer-plugins-bad-multiverse... or something like that that enables AAC/M4a playback. That's a package that depends
on gstreamer-plugins-bad, i.e. extends it. Unfortunately the whole web doesn't give me any
information on what that package contains, where it is, who built it, from what sources ...
So I'm stuck with the choice between my current Ubuntu (runs 100%, but ugly branding), the Gentoo (even in VMWare as fast as my Ubuntu on the real iron; doesn't play AAC audio), and the Fedora (looks good, is fast enough, has better configuration than Ubuntu IMHO, more "standard" than Gentoo, but plays almost none of my multimedia, even with those extra packages).
I'd really like to know what those Ubuntu hacks did to those gstreamer-plugins... (it's even the same version)