Jim, just to make sure
You are using the default Window Manager?
Did you reboot after installing? I didn't mention it but you have to do this because otherwise it doesn't show (menu are manually regenerated by a command which I haven't found..)

It's supposed to go in the default category (not system, not multimedia, something like "additionnal" or "supplements"). Don't know the name in english..

Really weird.
You could reinstall it for a quick try..
apt-get remove xmms
apt-get install xmms

And check attentively if this last command tells you something.
I'll look on my side what can create this problem.