Okay, well, Let me give this a shot.
being a member of the audio group means audio can play, not necessarily that xmms can run. Right? So...
chmod 755 xmms
to make it so the owner (presumably root, at this time) can read, write and execute, group users can read and execute, and the public can read and execute.
This is assuming that you haven't done that yet. If you have, maybe set it to 777. If /that/ doesn't work, its not a permissions issue, at least of the executable file.
Is this new with Lenny?