Hey Everyone: I had the same issue too. Have you tried the plugin superfish w/ a wp_listpages() function call in an unordered list? Superfish uses Jquery and an unordered list, based on the menu plugin
I tried that, and it worked for me. You get the flyout menu effect with the css/unordered list, and you get a dynamic menu; The menu items that show up are the pages because of the wp_listpages() function call. So when they add or remove a page, it reflects on the menu itself. The one thing you do have to do is style the list/menu for the different colors, but if you're running firebug you should be ok.
here's the link to superfish:
good luck, and hope this saves you lots of time ^_^