It would probably be less confusing if the menu also showed the current setting.
I'm not sure how you could do this, but there is some blank space in the top-level menu after you select shuffle from it. All the other options go away, and "Shuffle" is by itself in the center of the menu. Is that 8 pixels enough for a small text saying "Shuffle is ON - Least Recently Payed", or some variation?
It would probably be too much work to redesign the menu UI to do that, right?
Alternatively, you could bold or grey-out the currently selected shuffle mode so that it sticks out next to the other choices.
Anyone else have ideas?