Gosh there is so much discussion and code to wade through here and the linked thread. Has anyone packaged this as a plugin or instruction sheet?

How about this: http://www.zenphoto.org/documentation-official/zenphoto/_plugins---print_album_menu.php.html
The nightly's version even has the feature to be not context sensitive.

Okay tell me if this is correct though. When I added that function call it spits out a UL block of albums in random order, and does not list sub-albums. That's all it does?

Correction, it will list sub-albums if a parent is being viewed. But this random order is really bad...

Always try a little before posting...:-)

The print album menu has been reworked in the nightly, it now takes the correct order from the gallery class.
And yes, the the menu is context sensitive by default. This was done on request to save space and it makes sense. But the nightly version also has an option to disable that. The menu then shows the topleven plus up to 4 sublevels (zenphoto can have more sublevels of course, but it does not make sense to have more regarding usability and seo..)