It's not a "fix," since it is working as designed. If you understand one thing about the current shuffle, how it works becomes more intuitive. It can play songs from multiple playlists.
The default list that the shuffle plays from is the All Songs list. This is simply a list of ALL the songs currently on the shuffle, which is useful when you just want to "shuffle" the songs.
Even if you have only one playlist loaded on the shuffle, if you are playing from the All Songs list, you are not using that playlist. Therefore, when you set the shuffle to play-in-order (not shuffle), the All Songs list plays in alphabetical order, not the playlist order you want.
To play from the playlist (instead of the All Songs list), you need to use VoiceOver's playlist menu to switch from the All Songs list to the playlist. Then, the songs will play in playlist order (if the switch is set to play--in-order).
This document has instructions for setting up and using VoiceOver on the shuffle
http://support.apple.com/kb/HT4322
VoiceOver is basically the substitute for not have a screen on a shuffle...