you're using gnome right? check if you're programs are using oss as the sound server. in xmms, it's in options > preferences. as far as the other programs i'm not to sure. i know for me using xmms in gnome won't play anything if the sound driver being used isn't oss. i use kde, and xmms works only with the arts sound server.
anyway for mp3 support, you'll need to download and install the package found here:
http://havardk.xmms.org/dist/xmms-1.2.7-rh8-rh9-rpm/
edit: you may also need to check if gnome is starting up the sound server at start up. i think it's gnome start menu > programs > settings > multimedia