Veja o que funcionou para mim:
echo "deb http://repository.spotify.com stable non-free" | sudo tee -a /etc/apt/sources.list
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 4E9CFF4E
sudo apt-get update && sudo apt-get install spotify-client
Você pode fazer ping no repositório?
$ ping repository.spotify.com
PING repository.spotify.com (78.31.8.20) 56(84) bytes of data.
64 bytes from judith.lon.spotify.com (78.31.8.20): icmp_req=1 ttl=58 time=189 ms