Sorry to hear about this! I have tested multiple times on my test sites to try and replicate this issue, but this does appear to be an isolated issue, or incompatibility issue as @jackied1203 found. Thanks for all the help everyone (@smit_ralph, @imbecyl, @jackied1203) in trying to figure out the cause of this. @igloobob - you wont' want to leave your site with 777 permissions, that is very insecure and will leave your site wide open to hackers. You shouldn't have to go above 755, it should work with 755 permissions. Though, permission errors do indicate a write problem, so you may bring this up with your server host tech support and see if there are any settings they can adjust from their end. It may be they have additional security settings in place somewhere, you might ask if they have PHP Safe mode turned OFF and if they have it set to ON, request they turn it OFF. Another thing you might try is deactivating all plugins (including NextGEN Gallery) and then re-activate NextGEN Gallery only. If that doesn't do the trick, switch your theme to Twenty Twelve, > clear browser cache, and try again. Still having only NextGEN Gallery activated.
I hope that helps! :)