Yes, there seems to be a bug in the syncing mechanism itself. However, so far I've been able to prevent iTunes from causing this corruption by preventing it from syncing podcasts. Steps:
- Disable podcast sync (iTunes->Devices->iPhone/iPad/iPod Touch->Podcasts->uncheck "Sync Podcasts")
- Hit "Apply"
- Allow iTunes to delete all podcasts on iOS device
- Redownload desired podcasts in Podcasts.app
At this point, iTunes sync no longer corrupts the podcasts for me. I'm still subscribed to podcasts in the app and in iTunes, which now communicate via iCloud, but they have to download everything individually.
Further syncs under this paradigm reveal odd behavior. If you watch iTunes sync you might notice what I notice: it begins the sync, does an inventory of all the podcasts that are downloaded (where they appear in the sidebar beneath whatever iOS device you're syncing), and then they vanish. Once this happens, iTunes will not register that there are podcasts on the device again though they still - for me at least - exist within the app itself.
I'm still experimenting to see what the exact trigger is within sync though. I'm currently syncing all podcasts that are on my Mac with my iPhone to continue experimenting. My best guess/hypothesis is when you allow syncing of some podcasts via iTunes sync but are subscribed to additional podcasts within iTunes and Podcasts.app. How might this happen? All it would take is subscribing to a podcast in the app but never explicitly telling iTunes that you want this new podcast synced through the Devices tab. This confuses sync and Podcasts.app, and the problem appears. The podcasts are deleted, but Podcasts.app doesn't register that they're gone, and it throws up the error message.
But as axcess99 said, the workaround listed above might not work for you, so the best workaround right now that I can see is to prevent iTunes from directly syncing (sync that isn't iCloud or iTunes Match) until this is fixed.