That sounds strange. I've never experienced a problem using W3TC with NextGEN to date. I've just tested thumbnail creation again to be sure, but everything seems to be working fine (at least on my development server).
I'd be happy to take a look at your site/admin again if you could point out some specifics...
Is it breaking in the admin, or just not showing the thumbs properly on the front-end? If it's in the admin, is it happening when you regenerate thumbs, or when you upload new pictures? If it's on upload, is it via the "Upload Images", "Upload a Zip-File" or "Import image folder" options on the Add Gallery / Images page?