Tried reinstalling, didn't work. Found this answer in another thread and it worked:
Download from here instead:
http://download.spotify.com/Spotify.dmg
To make it work, I had to move to trash the current app.
Empty the trash.
Copy the app from the .dmg to the desktop.
Open the app from the desktop, valid all first-time execution secure warnings, and test the app.
Close the app.
Move the desktop app (copied from the dmg) to the app folder.