Hi Cais,
We didn’t change anything on the environment. The last change (I think), we switch to WP Super cache from Total Cache. And it’s been a while since we post an article using the Nextgen Gallery. I’m lucky enough, I had other WP Site that we can tested on and found out, that we had to disable the cache plugin to avoid the ‘permission issue’.
If you could involve a tester to simulate this error and found a root cause, that will helps a lot. NextGen Gallery has and will still be our choice though, it’s a great plugin.