Shuffle is not random. Spotify decided people don't like true randomness, so shuffle is more or less an algorithm of what songs in your playlist you seem to like more. Of course, this is based on (sometimes bad) guesses, and some songs you like might hardly ever get played because of this. Here Spotify probably thinks you really like the Beatles, so it will play them way more often than in true randomness.
I think Spotify still thinks this is an awesome feature and have no plans to change it. *sigh*