There is a long thread about this here.
In my case, the necessary steps to fix were:
- Log out and log in again (a full reboot wasn’t required)
- Run the Spotify installer
Probably unrelated, but my machine was sluggish and unresponsive after logging in again, so I ended up rebooting anyway.