We first suggest that you unlink Spotify from the Alexa app, and then add it again. Also, keep in mind that podcasts and local files cannot be played when streaming to another device. Can you try regular tracks available in the Spotify catalogue?
If that doesn't help, restart all your devices (and speakers), and make sure that:
I have a similar problem with my premium and have tried these steps to no avail. The major difference is that in my case Google home is working just fine with Spotify but my Alexa devices all tell me that Spotify is not supported on this device. I get this message on all four of my Amazon devices. But all of my Google devices are fine.
I deleted the Amazon app and removed and reinstalled everything but there's still some disconnect and I don't know where to go being the Spotify doesn't have phone support... 😞