What happens if you set up the syncing so that ONLY that one album is on the shuffle. Do the songs play?
If they do, it's possible that there is some confusion about how the shuffle plays its lists. When you play songs, you can play them from the All Songs list. This is fine if you are in shuffle mode, but if you set the shuffle to play In Order, the order on the All Songs list may be different than you expect. To play songs in a particular order, it would be better to create an ordered playlist, and play the songs from that playlist on the shuffle (not the All Songs list). To switch playlists on the shuffle, you use the VoiceOver button (press and hold). More info about using VoiceOver on the shuffle...
http://support.apple.com/kb/HT4322
If you already know the above, and it still does not work, I would do a Restore on the shuffle using iTunes. Select the shuffle in the iTunes sidebar, under DEVICES. Over to the right, on the Summary tab, click the Restore button. This will erase the shuffle, re-install its software, and set it to default settings. If there is some data corruption on the shuffle's storage causing this problem, a Restore should fix it.