Same problem here. I ducking hate Spotify for this stupid bug. I'm paying for premium service and all I get it's this bug. Come on. I do not want to restart my phone two times to listen to music. It is so frustrating!
Since Spotify is not fixing their major bugs for 4 f*****g months, I stopped paying for such a bad service and switched to D-E-E-Z-E-R premium+. Their app is much more reliable and I'm finally able to enjoy my music without such a Spotify-pain. So problem is solved for me...bye Spotify. :D
Are you serious? Why to restart phone every night? That is not solution. Smartphones should work without restarting. Mine is almost 8 days up. But I want stable and working applications when I'm paying money for it. And this bug is annoying. It can appear soon after restart also.
I´ve always had a habit of restarting my mobile phones almost every night. I have no clue if this is why Spotify app works fine for me. I also had problems with the same error earlier, but then I also restarted my phone almost every night, so I´m not sure if it helps.