I've heard this excuse before, that what we think is random really isn't, but when certain trends occur enough times, its pretty clear that there is some kind of algorithm or something in the coding that affects the shuffle.
I know random means random, but there are too many "random" coincidences and apparent patterns that occur to raise doubt that it truly is as random as Apple claims.
One such example, is that when using the Shuffle Songs feature (that shuffles all tracks on the iPod) I had 2-3 tracks from the same album (an album I had never even listened to yet) showing up within the first 40 tracks five times in a row. Numerous other songs showed up in at least 3 of the 5 "trials." Out of 8,000 songs.
On a playlist (of 300 or less songs is all I have tried), if you have multiple songs off the same album, you are far more likely to hear at least one other song off a given album within about 10 songs then you are to not hear a song off the same album. A specific example of this is on a playlist of 105 songs I have, there are 3 songs off one album, however nearly every time 2 of the songs will play within a 10 track range, and nearly as often all 3 songs will play within the same 20 track range.
I know random isn't perfectly spaced songs, but when certain things happen often enough, the odds of it become so low that even the "true random" explanation doesn't cover it.