Need help? Check out Spotify Answers for solutions to a wide range of topics.
For me I had to reconnect my Echo device to the WiFi and then just disconnect it from the outlet and plug it back in. That did the trick for me and haven't had problems since.
I'm having the same issue, tried all the steps above, but when I say "alexa connect to spotify" then i go my spotify app and choose my echo dot, it just stays stuck on "connecting"