Isso é causado por libgcrypt
. Você pode resolver isso por:
wget http://security.debian.org/debian-security/pool/updates/main/libg/libgcrypt11/libgcrypt11_1.5.0-5+deb7u3_amd64.deb
sudo dpkg -i libgcrypt11_1.5.0-5+deb7u3_amd64.deb
Se isso não funcionar, elimine spotify
e instale novamente a partir deste repositório.
sudo apt-get purge spotify*
Então
sudo add-apt-repository "deb http://repository.spotify.com stable non-free"
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 94558F59
sudo apt-get update
sudo apt-get install spotify-client