I am using the standard podcast app that comes with iOS 7. I have subscribed to about 8-9 different podcasts. Commonly I will take my phone with me when I leave the apartment, and then when I get on the subway I will attempt to listen to a podcast. Invariably, the podcast won't play because no cellular connection is available. To solve this issue I have indicated through the podcast app that I would like episodes to be automatically downloaded when they become available. However, they don't get automatically downloaded. This absolutely infuriates me.
Indeed, check the "Refresh Podcast" option and set it to every hour. Also, set Auto-Downloads to ALL
Do you have the "Refresh Podcast" set to an appropriate interval? I.E. The frequency with which you would like it to query the podcast server for new episodes.