I've watched this problem for a while. What I've seem to have noticed is that the player, when picking songs randomly, sometimes will pick multiple songs out of the same playlist and play them back-to-back.

For example, say you have the following playlists:

Alternative Rock
Classic Rock
Country
Hip-Hop
Singles
Swing

For the sake of argument, lets also assume there are tons of other playlists so that we can eliminate the "but that's only 6 playlists".

A typical random shuffle might look something like this:

Country song
Alternative Rock song
Random Playlist1 song
Swing song
Random Playlist2 song
Classic Rock song
Hip-Hop song
Random Playlist3 song
Random Playlist4 song
Singles song
etc...

However, I've noticed that when I shuffle, I tend to get playlists more like this:

Country song
Alternative Rock song
Random Playlist1 song
Swing song
Swing song
Random Playlist2 song
Classic Rock song
Hip-Hop song
Random Playlist3 song
Hip-Hop song
Random Playlist4 song
Singles song

I tend to notice grouping of songs from the same playlist. Sometimes it's from the same CD...sometimes it's from the same genre playlist.

Take a look yourselves for a week or two and tell me you don't notice this more often that what could fall under "chance".