I prefer to use VLC because it never gives me problems while Totem does. I'd like to uninstall Totem, so all file associations point to VLC. However I still want to have video thumbnails in Nautilus.
It's not actually uninstalling it but if you do
I think you have to leave the totem-common package installed you can remove all of the other totem packages and still have thumbnails.
After that check the preview tab in nautilus preferences
As you can see I have everything set to local and anything over 10MB won't get one. Meaning most videos apart from a few family videos. You can change this up to 4GB.
If you have changed this and still no joy then try deleting your ~./thumbnails folder go to your home folder and press ctrl+h to show the hidden files and folders. After this log out or restart nautilus and after a few minutes it should start to rebuild the thumbnail cache (ps good way to get some drive space back). If this doesn't work or nothing happens hours after restarting nautilus then a re-installation of Nautilus may be required. To do this open up Synaptic package manager and search for nautilus right click on the checkmark next to the package and selet re-install from the menu.
Hope this helps.