Okay, I have more information about the problem.
It does have to do with the pretty permalinks. According to my tests on a fresh wordpress install with no other plugins, here is what happens:
*This only happens to paged galleries on the a static front page AFAIK*
If you turn off permalinks completely, in both WordPress and Nextgen, it will work. Not really an optimal solution though.
If you turn on WordPress permalinks, but not Nextgen's, it will redirect to your posts. Strangely enough, it thinks it's on the home/index page.
If you turn on both, nothing will work. You can click the links to other pages, but it keeps showing the same first page of the gallery.
I have some more debugging to do, but I would like to get to the bottom of this.
More to come later.