Como parece que o pacote Spotify ainda está no estado "configurado", mas teve alguns de seus arquivos removidos, é necessário reinstalá-lo primeiro:
sudo apt-get install -f --reinstall spotify-client
Então você deve conseguir desinstalá-lo normalmente:
sudo apt-get remove spotify-client