My first experiences with MP3s on Linux was with RedHat 9 and Fedora Core 4 - Fedora 9. Yes, it was always possible to install the restricted codecs, but only recently were those instructions and processes made easier (and now, with recent distros, automatic). Maybe I was doing it wrong, but asking a user to install "restricted codecs" for something that Windows Media Player can do automatically isn't good for making users feel comfortable with your system.