Update, March 7, 2014: Improved shuffling has been rolled out on Spotify. More details at the Spotify Labs post, How to Shuffle Songs.
Users aren't wrong to complain, though. What people want isn't true randomness, but an even distribution with separation of similar tracks.
A random sequence might put 3 Michael Jackson songs in a row, but most users don't want that to happen when shuffle is enabled. We should bear this in mind when designing a shuffle algorithm. A simple notion of similarity based on artist alone should get us pretty far. (We can revisit this when users begin complaining that our primitive shuffle algorithm played four cello sonatas in a row.)
Dithering provides a visual analogy for the problem. Dithering is like a halftone pattern, used to create the illusion of continuous tones in a reduced-color image. Two particular methods of dithering are random diffusion and error diffusion.
With random diffusion (top), pixels appear clustered together. Error diffusion algorithms (bottom) take neighboring pixels into account and avoid clusters. In shuffling music, we seek to avoid the clusters in the same way.
By the way, Apple got this right 9 years ago.