I found a solution that worked for me when I was having this exact problem. Go to your Alexa app and click settings. Click on the "Music and Media" tab. Go to Spotify and then click "Disable Skill". Go back and re-enable the skill to link your Spotify account with your Alexa again. Hope this helps!
Edit: Apparently this only worked temporarily for some reason. I'll open a new post if I ever find a working solution and link it here.