Switching to the snap package solved the problem for me.
snap install spotify
The snap starts up fine, but then there are new problems, e.g. I can't open settings, or account. When I click the links nothing happens at all..
I think comments coming from people suggesting installing canberra and gail aren't related to the TS's problem, this problem has something to do with libcurl-gnutls. I have all the suggested packages installed already and I still have this problem. I managed to start spotify-client only once after reinstalling it but any subsequent attempt failed.