Is this a 3rd or 4th (current) gen shuffle? Based on what you said, I believe it is (because a 1st or 2nd gen shuffle works differently).
You are looking at your music on the shuffle in iTunes, when you select Music indented under the shuffle (in the sidebar), is that correct?
Over to the right, in the list of songs, are the songs "greyed out"? If so, the reason the songs are sorted that way and you can't change the sort order is because you have the shuffle set for automatic syncing. Previously, when you could change the sort order there, you probably had it set to Manually manage music.
The Manually manage music setting is on the shuffle's Summary tab. If you load music by dragging them to the shuffle in iTunes, that is the manual method. If you set up the shuffle's Music tab to sync from your iTunes library, that is automatic syncing.
When you use automatic syncing, you need to make changes on the playlists (in your iTunes library) that you sync to the shuffle, not on the shuffle directly. On the shuffle, use the VoiceOver button (press and hold) to switch to the playlist you what to play. The songs should play in playlist order, if the shuffle's switch is set to Play in Order. (If you play from the "All Songs" list instead of a specific playlist, I think the songs will play alphabetically, if the shuffle's switch is set to Play in Order.)
Please post back to correct any assumptions I made in my reply...