O bom pacote é chamado apenas de "spotify-client" e você pode remover a parte "qt".
sudo apt-get install spotify-client
Como você pode ver nesta saída, a do QT foi um pacote de transição:
$ apt-cache search spotify-client
spotify-client - Spotify desktop client
spotify-client-gnome-support - Transitional package for spotify-client
spotify-client-qt - Transitional package for spotify-client
EDITAR
De acordo com isso: link Você terá que ativar o repositório do universo. Entre na fonte de software e ative-a.
Isto é o que há dentro do meu /etc/apt/sources.list:
## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team. Also, please note that software in universe WILL NOT receive any
## review or updates from the Ubuntu security team.
deb http://fr.archive.ubuntu.com/ubuntu/ oneiric universe
deb-src http://fr.archive.ubuntu.com/ubuntu/ oneiric universe
deb http://fr.archive.ubuntu.com/ubuntu/ oneiric-updates universe
deb-src http://fr.archive.ubuntu.com/ubuntu/ oneiric-updates universe