Gimp es la herramienta linuxera para la que mas tutoriales encontre en la web. Yo mismo hice varios tutoriales o mini tutoriales para gimp. Ej: hacer sello con GIMP, como esconder rostros con GIMP, y mas.
En cuanto a videotutoriales supongo que todos conocen los podcast de GIMP que salieron y siguen saliendo hace mucho.
Pero, encontre un curso en videotutoriales de GIMP , son 28 videos que abarcan desde una introduccion al sistema operativo hasta manejo de recortes, capas, etc.