Steve Jobs in 2005: "You know we've gotten a lot of people that say our shuffle's not random. Well it really is random but sometimes random means you've got two songs from the same artist next to each other. Just happens randomly sometimes. And so what we've added is smart shuffle to actually make it less random - if you want. Even though people will think it's more random it's actually less random and what it is, in…
That theory also explained the disconnect between the complaints and Apples response. Apple would indeed be right that the music was randomized, but not continuously, as consumers expected.
It was never clear to me what the issue actually was, perhaps we really don't understand randomness.