Some songs dont play in my 4gen shuffle

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.

The songs on that album play properly, when you use iTunes on the computer to play them, correct?

Is this album a download from the iTunes Store, a download from elsewhere, or a music CD you ripped on that computer using iTunes? What is the format of the song file; when you do a Get Info on one of the songs in iTunes (from a right-click), on the Info window Summary tab, what does it say for Kind and Bit Rate?

Select the shuffle in the iTunes sidebar, under DEVICES. Click on the little triangle next to the shuffle, so that it points down. iTunes media types on the shuffle should "drop down" (indented under the shuffle). Select Music there. Over to the right, there should be a list of songs currently on the shuffle. Look for that album and its songs. Are they listed there?