Roll back to an older version of Spotify, that one should work much better. It's the same one as I have installed. The version featured in Welcome is a much newer version and personally, I don't like a couple things about it. 
Just tried and tested this in Ubuntu 15.10 (64-bit), so this should work:
- Uninstall any existing versions of Spotify.
sudo apt-get remove spotify-client
-
Remove the Spotify PPA from Software & Updates.
-
Install the Spotify package as specified on their Linux download page.
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys BBEBDCB318AD50EC6865090613B00F1FD2C19886
echo deb http://repository.spotify.com stable non-free | sudo tee /etc/apt/sources.list.d/spotify.list
sudo apt-get update
sudo apt-get install spotify-client
- We need to install
libgcrypt11, but this package is no longer present after 14.04. Fear not, we can grab a copy of the archive as outlined on this page.
32-bit: https://launchpad.net/ubuntu/+archive/primary/+files/libgcrypt11_1.5.3-2ubuntu4.2_i386.deb
64 bit: https://launchpad.net/ubuntu/+archive/primary/+files/libgcrypt11_1.5.3-2ubuntu4.2_amd64.deb
You should find version 0.9.17.1 installed and working much better.