Quería tener Clementine 1.2.3 en mi Debian Wheezy, así que manos a la obra.
Nos dirigimos al sitio oficial y descargamos el paquete para Debian Wheezy de 64 bits (que es en nuestro caso).

Luego entramos a la consola y escribimos en la ruta donde esta el archivo que recién descargamos:
cd Descargas
sudo dpkg -i clementine_1.2.3.wheezy_amd64.deb


En caso que tengas errores en la instalación, escribimos lo siguiente en la consola:
sudo aptitude install -f


Después de estos sencillos pasos ya podremos escuchar música con Clementine 1.2.3 en Debian Wheezy.