You can't convert purchased (protected) videos. That's why the options are grayed out.
However, according to this FAQ:
http://support.apple.com/kb/HT2729?viewlocale=en_US, "Videos purchased from the iTunes Store have FairPlay digital rights management embedded in the files and are in a format that can be readily synced to a video capable iPod."
The Apple document:
http://support.apple.com/kb/TS1497?viewlocale=en_US, Can't transfer videos to iPod, states "Any music video, TV show, or movie purchased from the iTunes Store is designed to be playable on the iPod and can be easily synced with iTunes 8 or later. Note: HD content cannot be synced to an iPod. When trying to sync HD content to your device, you will see a prompt like the one above stating that the file was not copied to your iPod because it cannot be played on your iPod."
So if you are trying to sync an HD video, you will get the error you described, but the SD version should work.
If your video is not HD, you can get help by going to this page. Scroll to the bottom and click the "Contact Us" button and fill out the form. Apple will get back to you by email within 48 hours.