O Spotify não é mais compatível com o Wine (a partir da versão 0.9.0, IIRC), portanto, executar o cliente Windows no Wine garante um resultado doloroso. No entanto, existe um cliente nativo oficial, as instruções de download estão aqui:
Eu não sei por que as pessoas ainda se importam em usar o Wine para Spotify, eu acho que eles apenas assumem que o Spotify nunca teria um binário nativo do Linux ... mas eles fazem!
Edit: Também deve ser notado que não é necessário o Spotify Premium para rodar o cliente de desktop nativo no Linux.