Bluegroove is a client written in ruby and gtk. It supports a medialib and playlists as well as song queuing. It also supports a tray icon with libnotify support for song changes.
This client is currently being Replaced by a Similar client written in C and gtk. http://bayles.id.au/dugite/ It's still in development and once it's moved forward a bit more it'll be properly released here.