Eu não sei como isso aconteceu (talvez alguém possa me esclarecer), mas a solução é simples.
Abra o /etc/apt/sources.list.d/spotify.list como root
gksu gedit /etc/apt/sources.list.d/spotify.list
Remova todas as informações do arquivo e substitua-as por
deb http://repository.spotify.com stable non-free
Salve o arquivo e atualize as fontes
sudo apt-get update
Agora você pode instalar o spotify
sudo apt-get install spotify-client