Ahora si que tenemos una versión nativa de Spotify, se acabo abrirlo con wine. Gracias a que desarrolladores del software usaban GNU/Linux ya lo tenemos aquí.

Aunque aun tiene una limitación, como no puede mostar aun anuncios solamente lo podrán usar las cuentas Premium, pero no creo que tarden mucho en arreglar este asunto.
Para instalarlo solo tendremos que seguir algunos pasos.
Abrimos nuestro source.list
sudo gedit /etc/apt/source.list
Añadimos el repositorio
deb http://repository.spotify.com stable non-free
Cerramos gedit y añadimos la verificación
gpg --keyserver wwwkeys.de.pgp.net --recv-keys 4E9CFF4E
gpg --export 4E9CFF4E |sudo apt-key add -
Ahora actualizamos los repositorios
sudo apt-get update
Y ahora sí lo instalamos
sudo apt-get install spotify-client-qt spotify-client-gnome-support