dag wieers (www.dag.wieers.com
) has an mp3 plugin for xmms called, strangely enough, xmms-mp3. If you use apt you can apt-get install xmms-mp3. Or, if you're feeling adventurous, you can remove the redhat xmms and recompile xmms from source from xmms.sf.net.
Personally I recompile from source. And I know it's a drag but mp3 being patented and all is a bit of a sore point with me at the moment - I'm burning all my stuff to oggvorbis.
haven't had any luck with the rhythmbox gstreamer-plugins-mp3 yet (I'm using FC2-x86_64)