Fácil y rápido, lástima que no esté activado por defecto este comportamiento.

$ sudo apt-get install libgsf-bin imagemagick

Con esto es suficiente, ahora puedes ver los cambios reflejados bien reiniciando la máquina ó matando los procesos de Nautilus: killall -9 nautilus.

Si aún así no te funciona, tendrás que borrar los archivos del directorio ${HOME}/.thumbnails.