Unfortunately, toggling shuffle mode on and off involves a number of steps:
- "Menu" back to the UI's top level
- select "Settings"
- set Shuffle to "Songs"
- "Menu" back to the top level
- select "Now Playing"
- proceed with listening or shuffling to next tracks