Even if you have only one playlist (the one with your podcasts) on your shuffle, you still need to switch to it using the VoiceOver button. I realize that you must be using the VoiceOver button, because you can find each podcast as its own separate "playlist."
So, it's not just the All Songs list and each separate podcast list. It's the All Songs list, a list of playlists (or just one playlist if there is only one on the shuffle), and the separate podcast lists.
My guess, especially since it does not work for you even after a Restore, and on two shuffles, is that you are not noticing that there is a playlist there that you need to select. You are trying to play the podcasts from the All Songs list (where they will not play), or from the podcast lists (where there are separated by podcast). If you select the playlist with the podcasts (not the All Songs list or the separate podcast lists), and the switch is set to play in order, they will play in playlist order.
The other possibility is that you do not have a playlist on your shuffle. You are dragging podcasts directly to the shuffle (or syncing podcasts directly), and they are NOT on a playlist on the shuffle. If that is the case, they will not play on the All Songs list, because podcasts do not play there, and the only place they will be available is from the seperate podcast lists.
See this Apple document about using VoiceOver
http://support.apple.com/kb/HT4322
in particular, Changing playlists and To choose an item from the playlist menu.