I am not sure exactly when it started, but even when I put iTunes on shuffle (iTunes 10.7 (21) for Snow Leopard on my iMac) it isn't random at all, there is a very clear alphabetical progression through song titles. Sometimes it will break out a bit, going ahead a little bit alphabetically, but it is largely linear.

Anyone else had this issue?
_________________________
We are STILL what we repeatedly do - insists Aristotle