Você está por trás de um proxy? Eu tive o mesmo caso que você, e eu tive que mudar no Spotify: Preferences > Proxy o "autodetect" para "HTTPS"
Estou usando o Spotify há 18 meses sem nenhum problema. Eu uso o Ubuntu 12.04. Hoje o Spotify parou e não inicia mais. Eu vejo apenas um flash rápido da tela de inicialização do Spotify e isso.
Não vejo mensagem de erro e fiquei sem opções que conheço.
Você está por trás de um proxy? Eu tive o mesmo caso que você, e eu tive que mudar no Spotify: Preferences > Proxy o "autodetect" para "HTTPS"