I have recently been working on another package for the Umbraco CMS. During the course of packaging the extension I hit a problem with the existing package actions that were available via the core and the PackageActionContrib project. You can easily add an Application Tree but none of them could successfully update an existing Application Tree during the uninstall process. As my package action modified an existing application tree in order to add a custom menu item I needed to write a new package action that could do this at install and then revert it during the uninstall process.
You can download the Update Application Tree Package Action and with a bit of luck this issue can be addressed at some point in the future or my package action can be submitted to the PackageActionContrib project for consideration. Make sure you drop the dll into your bin folder before you need to use the action.
Example package action usage:
[code language="xml"][/code]