The problem with mencoder, is that as far as i know, it only converts from one codec to another, and you often get loss of quality going from one lossy codec to another.
I use mencoder. It can handle about anything. Too much options, though, if you are looking for something easy.
I fully understand this, i wanted open source so i wouldn't have to deal with the extra crap. If i have to keep going out to the internet and downloading codec packs EVERY time i reinstall an OS (i do this quite often), it gets quite annoying. I suppose i could just make a backup of the Mplayer codecs and keep those on a cd, but it's still an inconvenience. PLUS i like to feel like i support open source whenever possible.
About the distros... Officially they don't support anything. Silly laws, patents, you know. You have to set repositories to install most stuff that can play an mpeg stream, because it's ilegal in many countries. Certainly, it's not in mine.
Metradistros like Gentoo don't have this problem though.