That file type should definitely play (it's the same as downloads from the iTunes Store). If you are using automatic syncing from that playlist where the songs are shown (instead of manually dragging files to the shuffle), do the following to confirm the song is on the shuffle. Select the shuffle in the iTunes sidebar, under DEVICES. Click the little triangle next to the shuffle to drop down the shuffle's content intended under the shuffle. Select Music there. Over to the right, are the songs that don't play shown on the list there?
If they are not shown there, the problem is that the songs are not actually syncing to the shuffle for some reason.
If they are shown there, there may be some data corruption on the shuffle. If you don't mind erasing it, the best thing to try would be a Restore. Go to the shuffle's Summary tab in iTunes and click on the Restore button. This will erase the shuffle, reinstall its software, and set it to default settings. Then, re-sync your songs to see if the problem recurs.
If you don't want to do a Restore just yet, you can first try deleting only those songs (with this problem) from the shuffle, and adding them back. You can also try adding other 256 kbps AAC song files (that are not already on the shuffle) to see if the same problem occurs with them. If the problem ONLY occurs with particular songs that are newly added to shuffle (not songs that are already on the shuffle), and not others, then the problem is more likely to be related in some way to those particular song files.