I'd assume that, since sound works in KDE and such, some other process might be using your soundcard constantly, maybe even KDE itself. /dev/dsp, which is the device for your soundcard, can only be accessed by one process at a time.
Try running xmms from an xterm, the error messages from a console are often more helpful than those you get in a GUI. If you still can't find the problem, post the error messages here and I'll give it a try
I remember that RedHat 8 does not come with the libs necessary to play MP3, but I found that those libs are the package you installed, after a Google/Linux search.
Can you play OGG vorbis files normally? If so, it might be a problem with the MP3 RPM because RH8 does come with support for OGG.
Give these things a try and post the results... and good luck