This worked for me: In the Alexa app go to Music, Videos, & Books. Under Music select Spotify. In the header, it was default set to "[Your name]'s Amazon Apps." Tap on this and change it to "[Your name]'s Echo." This will give you the Spotify setup page for the Echo.
When I first logged into Spotify through the Alexa app I used my email address and it wouldnt work. I changed this to my username as shown in the settings on my Spotify app and it worked perfectly. Based in the UK using a premium account.
I also had to connect through the Spotify app. The Alexa app said "app support not available" and I couldn't find a workaround. But when I did what you said and opened Spotify, I connected Alexa that way and now it plays.