I found the solution! At least in my situation.
I've never had a problem with nextgen gallery before.
I just migrated a client site to a Virtual Dedicated Server, I had this thumbnail generation issue.
Fortunately, I was able to fix the issue building the GD Library into the PHP configuration. If you don't have Root access to your host, you will need to submit a request, or call your host to double check the GD Library in the PHP build and if it's installed.
In my case, it just wasn't installed yet. but I've never run into this issue on a shared hosting account.
This is what convinced me:
This is how I did it on the dedicated server using the EasyApache wizard:
You can also check the compatibility using the box on the right of the Overview page in NGG. This also pointed to the GD issue.
There may be other reasons this issue could happen. But this work for me.