Nope, it's not with uploaded music. I don't upload any music to Spotify because it (as far as I know) doesn't sync across devices. This is the issue I'm seeing: https://community.spotify.com/t5/Android/Downloaded-songs-an...
I believe it's something with Android and restarting the device. It'll happen on my Android tablet, too.