I'm a KDE user and am very happy with Kaffeine, the KDE front end to the
Xine media player. Kaffeine adds a variety of UI features not present in plain-vanilla Xine. Both
mplayer and xine play everything I throw at them after I installed all the various non-free codecs for Fedora Core from the
Livna repository.
Ubuntu has
Automatix which is supposed to handle non-free items for this distribution. Not being in the Ubuntu/Debian world I can't comment on how well it works. I understand Canonical has been negotiating with Linspire to gain access to their repositories of encumbered software as well. So we might see a version of Ubuntu that contains legal support for mp3, MPEG, etc., though whether any such distribution can remain free as in beer is an open question given that Canonical will presumably be paying per-copy licensing fees.
All these matters are a nearly daily topic of conversation over on
Slashdot. Sometimes these discussions are even informative!