The solution that worked for me is to add a limitation to the smart playlist, selected by "random".
If your smart playlist does not already have a "selected by" limitation on it (at the bottom of the "edit smart playlist" window) then look at how much stuff is in the playlist, and set a limit higher than that (yes, this works. iTunes will still randomise the play order even if the rules in your smart playlist don't match enough items to fill that quantity) - whether you select by minutes, hours, number of items, megabytes, or gigabytes doesn't matter, so long as you don't set the limit too low. If my playlist normally has about 5 hours worth of goodies in it, I set the random selection to ten hours, so as to be sure that it won't be cut short unnecessarily. What iTunes will then do, is select from the items in your library that match the smart playlist rules, in random order, until either the limit is reached, or all the matching items have been used up. The result is a playlist in satisfyingly random sequence (so long as you are viewing it in iTunes sorted by the leftmost column.)
If your smart playlist already has a limitation selected by something other than "random" (e.g. least recently played, most recently added, etc.) then the only way I have found to get the result we are used to getting prior to Itunes 11 is to create an additional smart playlist that only has one rule: "Playlist is (your other playlist)" and to limit this new playlist to some high ceiling, remembering that it must be selected by "random".
This fixes the issue in 99% of cases. But what if you don't happen to like the play order that iTunes has randomly come up with, and you want to re-randomise again? Even this wish can be fulfilled. Just select all the items in your smart playlist (make sure not to accidentally select other things) and press "delete" on your keyboard. The playlist will become empty, but don't panic, it's just momentary, and then half a second later (ymmv) you will have the same items again, in a new play order. (nb: if your set limit is lower than the total items matching the rules, some of the items will be different. Randomly.)
p.s. in line with my last comment, of course you can also set a random limitation that is lower than the sum of all the items, if that's what you want to do. Sometimes this is a good idea, depending on how you use your i-device, and on what the quantity of stuff is that the rules in your smart playlist/s are matching. Usually my smart playlists are pretty specifically selected, so that I don't need to shorten them. (I mainly use them for spoken word material, so I have sunk a fair bit of time into getting my smart playlists right, so that I can sync and go without having to think about it.)
Hope this is clear, and hope it helps.