I finally got sick of xmms being so flaky and installed mpd which was discussed on gllug recently. It's brilliant!
In the Unix tradition, it is a collection of small tools that do one thing well, and nothing more. mpd is a music player that happily sits in the background as a daemon. A bunch of clients connect to the daemon and control what gets played. gmpc is clean, stable and nice. I've also got lirc working for the remote control and a tiny web-based client to allow control from the PDA. Neat!