I was also missing the easy shuffle by album of previous releases. I've got a solution for iTunes 11 that's just as good (for me anyway.) It's similar to some of the posts in this thread, but not quite the same. Here's what I finally settled on.
1. Set Controls->Shuffle->By Album. This sets the default shuffle mode to albums.
2. Create a Smart Playlist with the condition being "Media Kind" is "Music". This creates a playlist of all your music.
3. Check the "Live updating" box. This will pick up new music that you add, or existing music that you edit or delete.
4. Rename the playlist. I called mine "My Music".
5. Right-click the playlist and select "Shuffle My Music". It shuffles your entire library by album.
Here's something else I wish it would do. I like to display the playlist by album, but the currently playing song/album is not updated when I do that. I wish the currently playing album would be selected and expanded so I could see the songs and the one that is currently playing. For now, I have to find the album that is currently playing and manually select it to get this behavior.