Old thread, I know... Just thought for anyone who might be curious, the menu for random play can be found by holding down the volume center button.

Another good-to-know is that if you ever need to factory reset the unit, use the following three-finger salute: volume center button, menu, power. All three held down until the unit reboots.