Here's the fix. It's so easy that I wonder why Alex hasn't mentioned it. Ya think he doesn't know?
Anyway, check this out.
The pertinent part is this:
This issue can be resolved by increasing the memory usage allocation at a per-plugin level for PHP applications that require more grunt than others. It’s quick and easy!
1. Open an FTP connection to your root WordPress directory
2. Open /wp-content/plugins/nextgen-gallery/lib/gd.thumbnail.inc.php with your favourite text editor (e.g. UltraEdit, etc.)
3. On line #168 un-comment (remove the //) from before @ini_set('memory_limit', '128M');
4. Save and upload changes
5. Delete image/s that failed to generate a thumbnail and re-upload using NextGEN Gallery’s standard Upload Images feature
I don't know if this is still the case (it's from Dec. 2008), but the guy who posted the fix also said this:
Hey Graham, it’s an oldie but a goodie! Just make sure you re-apply the fix after auto-updating NextGEN Gallery… plugin function overrides at a WordPress install level is still only a dream.