I am really annoyed by the DJ feature missing too. In my case I used it to randomize my normal playlists and save the play order for use on my iPod. The other problem I have with iTunes 11's random feature is that I sometimes keep hearing the same song more than once.
Here is my random playlist work around:
1) Create a regular playlist of songs you want to randomize, you can use an existing one too.
2) Create a new "Smart Playlist"
3) Edit the new Smart Playlist and tell it to match the following rules:
-Playlist- -is- -point this to your playlist you used in step 1-
You can choose to limit the number of songs or not.
change "selected by" to Random
Leave "Live Updating" checked.
4) Depending on the source playlist size it may take a minute or so to fill in your new Smart Playlist that has been randomized.
5) Whenever you want to randomize the list again, just edit that Smart Playlist's settings and save.
Do not delete your original playlists, just use those to add new songs you want in your smart playlist. Live Updating on step 3 will automatically add them into the Smart Playlist. If you do delete the original playlist, the smart playlist will become empty as it is using the original playlist to pull songs from.