If the problem only occurs with certain podcast episodes (most others play fine), and they play fine in iTunes on the computer but continue to have the same problem on the shuffle (even after doing a Restore), my guess is that there is something unusual about those specific audio files that the shuffle cannot handle.
You can convert them to a different format using iTunes. Do a (right-click) Get Info on the podcast episode, and go to the Info window's File tab. Note the Kind and Bit Rate used for this podcast. Most podcasts seem to use MP3 ("MPEG audio file") format. Open iTunes preferences General pane, and click Import Settings. Choose AAC Encoder (if original is MP3). For Setting (bit rate), you should choose High Quality (128 kbps). OR if the podcast is purely spoken word, you can choose Spoken Podcast, which gives you a smaller size file that is mono (not stereo). Remember to change these settings back after you are done, because they are also used for music, like when you import ("rip") a music CD into iTunes.
Select the podcast episode (or episodes) with this problem in iTunes. From the menu bar, File -> Create New Version -> Create AAC Version. The new AAC version ends up in your iTunes Music library (as a song). Show your iTunes Music library sorted by Date Added or Album (to find the new AAC version). The Album is name of podcast; the Date Added is now. You should update the episode Name slightly, so you can distinguish it from the original; you can add "(AAC)" to the end of episode Name. Right-click it and select Get Info. In the Info window's Options tab, change Media Kind to Podcast.
The new AAC version of the podcast episode should now appear in your Podcasts library, alongside the original version. Try syncing it to your shuffle.