How to Programically add to the new WordPress menus

Pre WordPress 3.x I was using:

add_action( 'init', 'product_register' );
add_filter( 'wp_page_menu', 'custom_page_nav', 90 );

function product_register()
{
    //    register_post_type( 'product', $args );

    register_taxonomy( "catalog", array( "product" ), array( "hierarchical" => true, "label" => "Catalogs",
        "singular_label" => "Catalog", 'hierarchical' => true, 'show_ui' => true, 'show_in_nav_menus' => true,
        'show_tagcloud' => true, 'query_var' => true, "rewrite" => true, 'public' => true, 'capability_type' => 'post' ) );
    //'_builtin' => false,'_edit_link' => 'post.php?post=%d',
    ////////////////////////////////////////////////

}

function custom_page_nav( $menu )
{
    $taxonomy = 'catalog';
    $orderby = 'name';
    $show_count = 0; // 1 for yes, 0 for no
    $pad_counts = 1; // 1 for yes, 0 for no
    $hierarchical = true; // 1 for yes, 0 for no
    $title = '';

    $args = array( 'taxonomy' => $taxonomy, 'orderby' => $orderby, 'show_count' => $show_count, 'pad_counts' => $pad_counts,
        'hierarchical' => $hierarchical, 'title_li' => false, 'echo' => false, 'empty' => true, 'hide_empty' => true,
        'depth' => 0 );
    $links .= wp_list_categories( $args );
    //  $links .= wp_list_categories( array( 'title_li' => false, 'echo' => false, 'empty' => true ) );
    $menu = str_replace( '', 'Prodcuts ' . $links . '', $menu );
    //
    return $menu;
}

How do I do the same thing with the New WordPress 3.x menus.
Using another post on here I was able to figure out how to make a new menu but not add the custom taxonomy items to it:

function register_typenav()
{
    $mainnav = wp_get_nav_menu_object( 'Products' );

    if ( ! $mainnav )
    {
        $menu_id = wp_create_nav_menu( 'Products' );
        // vav item for each post type
        $types = get_post_types( array( 'exclude_from_search' => false ), 'objects' );

        foreach ( $types as $type )
        {
            if ( ! $type->_builtin )
            {
                wp_update_nav_menu_item( $menu_id, 0, array( 'menu-item-type' => 'custom', 'menu-item-title' => $type->
                    labels->name, 'menu-item-url' => get_bloginfo( 'url' ) . '/' . $type->rewrite['slug'] . '/',
                    'menu-item-status' => 'publish' ) );
            }
        }
        if ( $mainnav && ! has_nav_menu( 'primary-menu' ) )
        {
            $theme = get_current_theme();
            $mods = get_option( "mods_$theme" );
            $key = key( $mods['nav_menu_locations'] );
            $mods['nav_menu_locations'][$key] = $mainnav->term_id;
            update_option( "mods_$theme", $mods );
        }
    }
}
add_action( 'init', 'register_typenav' );