Sometimes when audio route changes, but also fairly regularly when waking my Mac from sleep, Spotify will complain about not being able to play the current track. Restarting the app is the only way to restore functionality.
First of all, have you tried a clean reinstallation?
No, haven't throught to try that. I'll give it a shot and see if the problem goes away, though I'm not optimistic.