I was having a similar issue with St. Vincent not playing. It's cleared up so it seemed like it was a license or server side issue. I did recenetly sign out of the devices it wasn't working on. Reinstalled them from their download sources (Apple App Store and Spotify's website) and it's working now. If you do talk to a Spotify rep through the customer service portal they will want you to import your playlists to an entirely new account using that same email.
It's super frustrating. I was dealing with this late last week and earlier this week. It seems to be a rolling bug. I suggest signing out of your account and reinstalling a fresh download of the current app or desktop client and seeing if that works and isolating if it works or doesn't work on mutlple devices.
It's a rolling rights issue as far as I can tell. Signing out of your devices and signing back into them helps but it also seemed to work itself out for me. I can tell you trying to play from one device that isn't playing the song and resuming on another device does seem to make the error spread and vice versa.
Spotify's costumer service was really not helpful but the issue I had resolved either on its own or logging in and out of the devices. It's the most frustrating thing and i wish there was an actual quick fix for it.