I'm a Linux newbie, too. I had a similar problem with RedHat 8.0. is that the version you are using?
RedHat removed portions of the XMMS package, because of concerns with mp3 licensing. I wonder whether there was some conflict between RedHat and Michael Robertson, who founded Lindows and pioneered mp3.
There is an easy solution. Go to the XMMS home page - http://www.xmms.org,
and install a patch they have for RedHat's XMMS. It solved my problems.
Also, have you configured XMMS to work as a plug-in? Do so, and when you are prompted which application to use, go to advanced and type in xmms.