well I do have the most recent version of iTunes and iPod software, so thats not an issue.You should be able to do this. i just checked my library and I have 2 playlists that are set on shuffle and the rest are not. Some also have different view options like 'equalizer' in place of 'last time played', etc.
If you have the most current version of iTunes, this should work.
Is my only option constantly switching "Shuffle: Off" to "Shuffle: Song" on my iPod? or can I get certain playlists to randomize?