Since there is nothing "out of the box" that will do this, I decided to work on my own solution. I found a great gallery called
Gallery which supports multiple galleries and multiple albums within each gallery. It also supports permissions per gallery and per-album, does thumbnails, etc.
I read yesterday that a new version was recently released that worked with phpNuke and since I'm running the beta of vbPortal (the nuke port for vB) I decided to install it and see what happened. The good news is that it only took me about 4 hours to get it hacked in, the bad news is that I don't know if it works without having vbPortal installed.
I still have a couple more things to do, and I am also going to attempt to hack in UserGroup based permissions as well, but since I'm new to how vB works and PHP in general that may take a bit longer. I have a couple more things to cleanup in the code as well, then I'd be willing to post it for anyone who is interested in working on it.