I think it is a bug in the iOS Podcasts app. Here is my reasoning.
Yesterday is the first time I experienced this issue. I found that I did, indeed, have Sync Podcasts checked in iTunes. So I unchecked it, and applied it, so a sync started. I was in the process of listening to a podcast at the time that I had added back to my iPhone via the "delete and add old episode" method.
Sync finished, I continued to read through this post.
Then, i figured, let me try something.
Went to another podcast that I redownloaded to the phone prior to the sync where I unchecked the "sync podcasts" option. Got the error again. Redownloaded it, played fine.
Then I went back to the podcast I was listening to during the sync, that continued to play fine post-sync. The error popped up and the podcast refused to play.
I have quit iTunes for now (finding I rarely need to sync it anyway anymore) and everything is working as planned. I am tempted to just turn WiFi syncing off for now to prevent it from happening, and allowing me to continue to use Home Sharing and access videos from my Apple TV, but looking for a way to submit this as a bug.