You video res, make sure you are not using generic settings.
Check V & H rates etc. Make sure you are using the recommended res
setting. Its the default optimal one. Remember that the quality of the
image file, determines the quality of the thumbnail to a degree.
Generating thumbnails also takes up a lot of ram, which affect the
quality of the TN generated as well. Open kcontrol and check into all
your video related settings.
Enable anti-aliasing if you have the video ram. Some embedded viewers
perform better with some combinations, so experiment.

Good luck

Kate