Você perdeu a etapa 2 das instruções às quais vinculou:
# 2. Add the Spotify repository
echo deb http://repository.spotify.com stable non-free | sudo tee /etc/apt/sources.list.d/spotify.list
Essa é uma etapa essencial, pois adiciona o repositório do Spotify. Se você não adicioná-lo, não poderá usá-lo para não encontrar o pacote. Então, basta executar o comando acima e continuar com as etapas 2 e 3 da sua pergunta.