Although it is still developing as we speak and they've released the 0.7 RC version which includes numerous improvements over the previous versions such as ...
*. MusicBrainz tag download support.
*. Added a cue file manager.
*. Network proxy support.
*. Now you can choose to make it show only "duplicate files" or "untagged" files only are just a few to name.
If you don't like KDE and just want everything to be pure Gnome, then you may not like Clementine ;-) since it is based on the Famous KDE audio player Amarok. Anyhow, for installing please visit this Google Code page for Clementine (they have .deb and other builds available, so you can just install it easily).