As far as I am concerned, XMMS is still the real deal.
It may be legacy software, but, if you don't care about playlists and tags and rankings and that sort of stuff--and I don't--it is still the best. And it can use all my old Winamp 3 skins. Also, a search for "XMMS skins" turns up lots of native XMMS skins still available.
Otherwise, I use VLC, because, if it won't play in VLC, it won't play on Linux.
There's a *.deb here:
http://www.pvv.ntnu.no/~knuta/xmms/
It works on Lenny and Squeeze.
I had it running on Lenny and it survived the upgrade to Squeeze.