To avoid misunderstandings this is labelled "Autoshuffle playlists when loaded" for some time now. I do not remember how it was labelled in RC2 but this option only applies to playlists loaded from harddisk (e.g. previously saved sessions).
If you do not feel comfortable with the regular "shuffle" button you maybe want to have a look at the audioscrobbler plugin which automatically fills the playlists e.g.:
- with similar tracks based on the current running track
- with totally random tracks
- with your favorites
- with unheard tracks
- etc..