I had some problems after upgrading nextgen and wp. A couple of things that fixed it, just in case.
1. Nextgen actually prompted me to update my nextgen gallery because it was out of date. I don’t remember which page this prompt was on. I think it was on the main gallery page. This was just a click of the button and easy.
2. I needed to update my permalink structure in WordPress from the settings page.
These probably aren’t your problems but thought I would post in case.