Here's how I finally fixed these problems.
1. With the device unplugged, go to your Collection, right-click on each show with problems and tell it to Never Sync that show.
2. Plug in your Zune, let it finish sync to remove these shows from the device.
3. Unplug again, go back to your collection, right-click and Sync With device on each show.
4. Plug the Zune back in and let it re-sync, correctly this time.