I came across this post, linked from slashdot. In it, Steven Levy speaks somewhat philosophically about the iPod shuffle feature, and the well-documented non-randomness problem. He comes to the conclusion that there is no deep conspiracy to play certain artists and the iPod is not telepathic, we are simply illustrating two well-known cognitive phenomena: our general failure to understand statistics (see John Allen Paulos's Innumeracy for an excellent discussion), and our desire to see patterns where there are none.

The article is interesting, but does not discuss what to me is the most interesting part of the "problem". Does their shuffle feature have a bug? Their development team originally said no. They insisted their random number generator was a perfectly valid algorithm. I'm sure that it is. However, that isn't the bug. The bug is giving people "good" randomness instead of what they want, which is something that feels random to a person. Of course, they are a customer-oriented company and fixed the bug. From the article above:

But the non-randomness illusion was so prevalent that ultimately Apple felt compelled to address it. In the version of iTunes rolled out in September 2005, there appeared a new feature: smart shuffle. It presents iPodders with a scroll bar that "allows you to control how likely you are to hear multiple songs in a row by the same artists or on the same album". If you pull the lever to the right, the iPod will mess with its usual distribution pattern, intentionally spacing out songs by a given artist. As Jobs explained it in his presentation the day the new iTunes rolled out, he gave what he hoped would be the last word on the Great iPod Randomness Controversy: "We're making it less random to make it feel more random."

I think the last quote really sums it up. They added a feature to fix a bug in perception despite the fact that there is no bug in execution. This is a lesson that many of us have to learn the hard way, when we continue to fight a losing battle to avoid fixing a bug because we did things "right", but it turns out it isn't what was wanted.