Automatically add new custom posts to a submenu within a WP 3.0 menu

I am working on a WPMU 3.0 site where we have some custom post types. We are using WordPress 3.0 menus. In the top level menu items we have a menu item for each of the custom post types. When the user adds a new custom post type - we want the post AUTOMATICALLY added to the appropriate top-level menu option. Yes, the user could add the post manually to the menu, but they prefer not to do this extra step that they overlook. They want it done automatically based on the publish status of the post. Any suggestions on how to accomplish this?