Last post on this ... I was too hasty ...
I went to look for a another great gallery, saw one, and it turned out to be based on nextGen, with the same problem too ! Except that it gave a notice that memory was exceeded (unlike Nextgen, no notice at all).
Argh, why are IT folks so talented in making programs, but not too much in communicating with people ? :) Nextgen should have a big warning that its default settings is not meant for folks who value photography or big size images.
Anyway, after being warned about memory by the other program, I did a search and finally found the solution. Change the default settings of Nextgen regarding memory. It has a note inside the php file to change for bigger images, but no such info in the FAQ.
Uncommenting the line mentioned in the link below did the trick for me :
http://www.visser.com.au/blog/thumbnail-generation-php-memory-limit-nextgen-gallery/