The thumbnails in Nautilus do not seem to be regenerated, once the correct libraries or codecs for different video formats are installed. If one has opened the folder filled with videos without installing codecs, there's a chance they have been blacklisted by the thumbnailer.
The solution is to open the /home/[username]/.thumbnails folder and delete all files in fail folder.
After that, to restart Nautilus from a command line, do:
Now it should regenerate the thumbnails.
If this does not work, please make sure you are able to play those videos, and correct libraries to play them are installed.
You can also try deleting all files in the all folders in.thumbnails.