There does seem to be some bias in the shuffling, but it's not related to the ratings.
I have a "Top-Rated" playlist of close to 200 songs (weighing in at 15 and a half hours) that I listen to fairly frequently, and all the songs are rated 4 or 5 stars. As it's such a long playlist, it's fairly infrequent that I'll actually get to listen to it all the way through before I need to close iTunes or want to listen to something specific, both of which lose the current "shuffle".
Having reconstructed my iTunes library from scratch some time ago (as my library file got corrupted somehow), all my play counts had been reset to 0 and I had re-rated all the songs at the same time (save for a few recent additions, which are statistically insignificant). When I look at my shuffled list, though, I can see the songs shuffled near the top average about 11 plays each while near the bottom it's closer to 8 or 9. It's really easy to eyeball this as there's a lot more double-digit counts at the top of the list (no, I didn't calculate anything). (The ratings seem to be equally distributed throughout the list.)
If the shuffling was simply not maximizing the deviation, one would expect to see the higher play counts distributed equally throughout the shuffled list; although perhaps many of the songs from the same albums would have similar play counts. Instead, I see a definite tendency for the higher play counts to be shuffled near the beginning. This implies that the some songs are getting preferentially shuffled near the beginning (though not dramatically so), and then as I listen to one quarter, or one half, of the playlist, only those songs get their counts incremented.
- an itunes user