I have exactly the same situation: same phone, same software system, Premium, etc... And exactly the same happens: cannot store on my SD Card!! And it is not a problem of my SD card, since other Apps can write and save data on it! And I also already did try those several troubleshooting steps with uninstalling and reinstalling everything, and still doesn't work! I'm getting really mad at it, because I pay a monthly amount for Spotify and I am not being able to make the most out of it due to not being able to store music in my mobile device!! Help me please!!
Do you have offline music already downloaded to internal storage? maybe this is causing an issue where you may need to delete any downloaded stuff, log out of the app, but not delete it, re sign in then try storing on SD?