Since updating to iOS 6 on my iPod touch I have had problems with my podcasts. My biggest gripe was not being able to incorporate a podcast into a playlist but then my podcasts would randomly stop about ten minutes into a run. Not good when you are trying to complete an interval run! I would also find that my iPod would say that the podcasts were 'ready to download' when they were obviously already downloaded. I thought this was peculiar to the C25k+ podcasts but then the same thing happened with my Suz's 5k to 10k ones as well.
Reading around the Internet I found that if you delete the podcast app then your podcasts will reappear in your Music app as before (you will need to reboot your iPod for this to work). From here you can then incorporate them into a playlist as before and they don't seem to want to download all the time. The downside with this method though is that you cannot download new podcasts through your iPod but you can download them through iTunes on a PC and sync them across. I've tried it and so far so good for me although I wouldn't recommend the method just as you are about to step out the door just in case it goes pear shaped!
I am hoping that Apple update their Podcast app very soon and fix these bugs but, until then, this is the only workaround that I have found.