Why won't certain songs play on my ipod shuffle, but play on all my other apple devices?

Every download from the iTunes Store should play (if it's not a video). If it's from another source, what type of file is it. You can do a Get Info (from a right-click) on one of those songs and reply back with Kind and Bit Rate (from the Summary tab of the Info window).

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.

There was probably some data corruption on the iPod's storage that prevented any new songs from being stored properly. A Restore erases (reformats) the iPod's storage, so the data corruption issue went away.

Kind of a bummer, time consuming to get my playlist back for running!

You should create one or more regular playlists in iTunes that have the songs you put on the shuffle, such as your "running" playlist. You can then set up the shuffle's Music tab in iTunes to automatically sync only those playlists to your shuffle. You can have multiple playlists on the shuffle and switch between them using the VoiceOver button, as described here

http://support.apple.com/kb/HT4322

Then, your iPod's playlists already exist in iTunes, so you don't need to "manually" recreate them after doing a Restore. Just Restore and re-sync. It will be done in a few minutes, automatically. Another "every day" advantage is that the iPod does not need to be connected to your computer when you update those playlists. You can update them at any time, and the next time you connect the iPod (or when you click the Sync button), any changes you made to those playlists will sync automatically to iPod.

I have the same problem i've done all the steps but they still wont work

If you have done a Restore on the shuffle, and particular songs do NOT play on the shuffle, but other song files of the same type DO play fine, the problem is likely to be related to those songs that do not play (not the shuffle).

I would re-download the songs (or re-rip them if they came from a CD).

Actually quite a simple fix. It says your file is an AAC But it isn't. Open your iTunes library, select all songs, right click, then choose make AAC copy. Or mp3 copy. Which ever it gives you the option to choose from. YOU'RE WELCOME!!