Eu recebi as mesmas mensagens de erro exatas. Estou executando o Ubuntu 14.04 de 32 bits. O que funcionou para mim foi atualizar a chave pública para spotify-client:
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys D2C19886
Então sudo apt-get update --fix-missing
O --fix-missing
pode ser redundante ou desnecessário, mas apt-get
sugeriu enquanto eu fazia muitas atualizações no meu computador.
Eu não sou especialista no assunto, mas funcionou. Eu pensei que era um problema com a atualização do pacote spotify, mas descobri que eu já tinha a versão mais atualizada.
No seu caso, com uma nova instalação, e possivelmente perdendo o pacote spotify (ou o que quer que tenha acontecido), eu sugeriria o elgastelum aconselhado e atualize o arquivo sourcelist antes de reinstalar ou atualizar:
echo deb http://repository.spotify.com stable non-free | sudo tee /etc/apt/sources.list.d/spotify.list
Espero que meu conselho não seja confuso ou "impreciso". Eu não sei tudo, mas o que eu sei, eu tento compartilhar. Felicidades e boa sorte!