I'm not sure if anyone has managed to do this yet, but i've successfully hacked PHP Photo Gallery (http://www.jeroenwijering.com/?item=PHP_Image_Gallery) to work with WordPress. The original didn't come with theme support, so I did some modifications and came up with http://www.urbanskaters.co.uk/wp-gallery.php
If anyone wants the code, it's only one script file with a few supporting txt files, get back here and i'll upload it for public download.
This is NOT a plugin. You simply drop the main files and the sub-folders with your photos in the root of your WordPress folder, add a link to your site pointing to it and away you go.