This happened to me after an upgrade of WordPress and/or the plug-in itself.
I was getting the ‘ID #: A failure occurred’ as well as the PHP error:
[27-Jun-2014 11:46:01 UTC] PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 16668 bytes) in [redacted]/plugins/nextcellent-gallery-nextgen-legacy/lib/gd.thumbnail.inc.php on line 436
Thumbnails were either not generating or when they were generating they were extremely posterized and degraded. One of the upgrades seemed to have wiped out ALL of the settings (leaving every settings field with an empty string/null value).
My solution: Find or make another WordPress site with NextGen installed. Copy over each setting exactly (ESPECIALLY make sure you have a graphic library selected, the path to mine was /usr/local/bin/ which seems standard, and ensure that thumbnail quality is not blank)
Hope this helps someone!