There is one key difference between your new shuffle and your old one, if your old one was 1st or 2nd gen.
The old shuffle acts like it's one playlist. It's like a "mobile playlist" that you can disconnect from iTunes and take with you. The new shuffle is more like the "bigger" iPods. It can have multiple playlist. Since it does not have a screen, you use the VoiceOver feature to interact with it.
First, check that the playlist is actually on the shuffle. On the old shuffle, the whole shuffle acted like one playlist, so you did not need to worry about the playlist being on the shuffle. Select the shuffle in the iTunes sidebar, under DEVICES. Click the little triangle next to the shuffle to "drop down" its content, indented under the shuffle. Your playlists should be shown there. If they are not, you may have loaded the shuffle from a playlist, but the playlist itself is not on the shuffle.
If your playlists are shown there, you need to switch to the playlist when using the shuffle. If you play songs from the All Songs list on the shuffle, with the switch set to play-in-order, I believe they play in alphabetical order. Use the VoiceOver button (press and hold) to swtich to the playlist, as explained in this article
http://support.apple.com/kb/HT4322
(see Changing playlists and To choose an item from the playlist menu)
Once you select a playlist (instead of using the All Songs list), your songs will play in playlist order. Even if you have only one playlist on the shuffle, the All Songs list and the playlist are separate choices.
