I just made it work suddenly. The solution was to play around with the languages. That means I logged out from Spotify. Logged in again. Had some problems with the log in and had to change the language to US English and to enter my adress, with postal code and street. Then I could log into spotify again. After that I chose Spotify as my standard player, but it did not work. So I changed back the language into German and worked. Hope I could help someone. Cheers.
I know this is going back to 2016 but just for anyone that has the same fault I had the same error and it was the email address I had saved on Spotify wasn't the same as I was using for Alexa and when I updated so that both were the same it connected ok and all working ok now 🙂
This error continues to happen CONSTANTLY. For some reason my two echo dots seem to connect more regularly and are viewable in the available devices list (but not 100% of the time) while my brand new 2nd gen Echo is almost never available or drops out of availability in the middle of listening to a song.
The only solution I can find is to unlink and relink the Spotify account in the Alexa app, but I have to do this constantly. I’m talking every single time I want to play music only Echo.
Im highly disappointed in this software. It’s making me want to return my Echo and cancel my Spotify. Honestly, very disappointing.