If by thumbnails you mean movie specific thumbnails then:
I know you said you have tried everything else but... well this may be a completely pointless post but: have you tried copying the files to another storage device and then deleting the original file and copying them back.
If you mean just the standard AVI (etc) thumbnails, then i would have thought they would be program specific for you so have you tried reinstalling the programs?
I guess you didn't back up your registry?