This is what I was thinking, as I was driving in, and heard the same song. It was an iPhone, and it was my impression that this is how the iPhone worked. Now, my iPhone did something else weird, it randomly dropped songs from being downloaded, so songs 'disappeared'.

One other thing, I just got a new car, and this was the first time I was using 'next' using bluetooth. So, as I was driving in, I was in my head trying to figure out whether the phone now only had 100 songs downloaded, or whether this bluetooth 'next' function on shuffle was picking a random song from the list, rather than 'next' on a shuffled list.