(Have no fear, This problem is rhetorical and my solution is below!)
I've been struggling with this problem today, the solutions posted work but having two lightbox plugins conflicts and the jQuery lightboxes posted have two problems. They dont look as good as the more classic lightboxes and, more importantly, it requires you to have the rel=lightbox tags put in - which isn't convenient as my theme is already based around the plugin adding them automatically.
There is, in fact, a very simple solution. I used NextGEN gallery (obviously) and WP-PrettyPhoto (my lightbox).
To make these work together you need to go into the settings for WP-PrettyPhoto and set the rel tag to something ie "Lightbox". Then go into the NextGEN settings and to the Effects page, in the box with the rel tag "Lightbox[%galleryname%]" change this to the rel tag you set in wp-prettyphoto, we used "lightbox".
WP-PrettyPhoto has a Auto-Prettify option which will add lightbox to all image links on the site (although strangely not the ones in NextGEN) and the "lightbox" rel tags you added make it work with NextGEN.
The only downside is that occassionally PrettyPhoto wants to cut the bottom 30% of the close button off but thats a problem for another day.