I've been having this issue recently where a song that I added to the queue about a week ago apparently got 'stuck' and will pop back into the queue sometimes when I start playing something new, be it an album or playlist.
This is not systematic, but quite often the song will play right after the playlist or album's first song.
I posted this in the Android forum, but the issue doesn't seem specific to the Android app - I've had it consistently with two linux PCs and a Spotify-compatible Yamaha AV receiver as well, so I guess it's something connected to my account rather than a specific playback device.
When I initially added the song to the queue, about a week ago, I noticed that Spotify was acting a bit flaky. Playback stopped unexpectedly, and I found one song (not the one that got stuck, another one) that wouldn't play on one device but played fine on my phone. Maybe something got borked in the backend at that time?