I'm having the exact same problem. Galleries were working fine up until a few days ago. Then, it started spitting back an "error 500, internal server error" when I was adding images to galleries. Next it would not thumbnail anything, returning either a failure re:
[XMLHttpRequest] or telling me that the jpg's I was uploading were not of the correct file format. So I deactivated the plugin, deleted it and then deleted everything off of the server. I downloaded the latest version of Nextgen, uploaded it to the server. When I went to activate it, the activate link on the admin screen would return a 500 error. So I ticked the box, selected 'Activate' from the dropdown menu, clicked 'Apply' and it would activate. However, when i went to changes the settings, etc., it would also put me into a loop of 'databases are outdated, please upgrade NextGen', then I would get a success screen w/ a continue button that would return me back to the 'databases are outdated....' screen-endless loop. Help!