I discovered Clementine some time ago.
There is not any package for Ubuntu or Debian, but the official site gives you a .deb for your favorite Ubuntu version. And you'll also find Mac OS X and Windows versions...
A small click on the good .deb file for your Ubuntu distro and it should install.
I tested tons of players (Amarok, Rythmbox, old XMMS, Exaile, Listen, Totem...).
Clementine is based on Amarok, it's far simpler and integrates very well in Gnome desktop using Qt4 librairies.
I'm happy to know this software and I recommend it to you.
