I'm facing this issue since I chenged Huavei P9 to Samsung Galaxy 10.
I've tried all sollutions described here, but spotify randomly stops playing anyway. This occures more often when I'm listening something new, some new album. Sometimes when I wait a while, the music starts plaing again. But most often I'm applying a silly sollution:
Setting-> Applications-> Spotify Force Stop. Then I'm running Spotify and the music is playing till the next unexpected stop.