While there is probably a better way to do this, here’s my first shot at adding custom taxonomies to the menu. Assuming that you have a custom taxonomy created, say ‘wps_projects’. What are your thoughts?

add_action( 'init' , 'wps_add_custom_tax_menu_item' , 15 );
/**
 * Adds terms to a specific part of the menu by location
 *
 */
function wps_add_custom_tax_menu_item( ) {
	// Edit these three variables
	$top_menu_item_name = 'Projects';
	$taxonomy = 'wps_projects';
	$menu_location = 'primary';

	// Get menu by location
	$menu = wp_get_nav_menus( array( 'location' => $menu_location ) );
	$menu_id = $menu[0]->term_id;

	// Get terms from wps_projects
	$term_args = array(
			'hide_empty' => false,
			'parent' => 0,
		);

	// Get only top level $terms
	$terms = get_terms( $taxonomy , $term_args );

	// Get items
	$items = wp_get_nav_menu_items( $menu_id, array( 'post_status' => 'publish,draft' ) );

	// Set parent item id
	$default_parent_id = $parent_id = wps_get_nav_menu_item_id(  $top_menu_item_name , $items );

	// Filter items to only the part of the menu necessary
	$items = get_nav_menu_item_children( $parent_id , $items );

	// Cycle through top-level terms
	foreach ( $terms as $term ) {

		if ( !$term->term_id || $term->term_id == 0 )
			continue;

		// Check for term in menu
		$match = wps_check_nav_menu_items( $term , $items );

		// If not found, add
		if ( $match == false ) {
			wps_create_nav_menu_item( $menu_id , $term , $taxonomy , $default_parent_id );
		}

		// Get term's children
		$term_args = array(
				'hide_empty' => false,
				'child_of' => $term->term_id,
			);

		$child_terms = get_terms( $taxonomy , $term_args );

		// Set new parent item id
		$parent_id = wps_get_nav_menu_item_id( $term->name , $items );
		if ( ! $parent_id )
			$parent_id = $default_parent_id;

		if ( $child_terms ) {
			// Cycle through children
			foreach ( $child_terms as $child_term ) {
				if ( !$child_term->term_id || $child_term->term_id == 0 )
					continue;
				$match = wps_check_nav_menu_items( $child_term , $items );

				if ( $match == false ) {
					wps_create_nav_menu_item( $menu_id , $child_term , $taxonomy , $parent_id );
				}
			}
		}
	}
}

/**
 * Returns true/false whether an item is already in the items (via its items)
 *
 * @param   object    the parent nav_menu_item ID
 * @param   object    nav_menu_items
 * @return  boolean   returns true/false
 */
function wps_check_nav_menu_items( $term , $items ) {
	$match = false;
	foreach ( $items as $item ) {
		if ( $term->term_id == $item->object_id ) {
			$match = true;
			break;
		}
	}
	return $match;
}

// Creates a nav_menu_item
/**
 * Returns true/false whether an item is already in the items (via its items)
 *
 * @uses    wp_update_nav_menu_item
 * @param   object    the parent nav_menu_item ID
 * @param   object    nav_menu_items
 * @return  boolean   returns true/false
 */
function wps_create_nav_menu_item( $menu_id , $term , $taxonomy , $parent_id , $args = array() ) {
	// Setup Menu Item Args
	$args = array(
		'menu-item-object-id' => $term->term_id,
		'menu-item-object' => $taxonomy,
		'menu-item-type' => 'taxonomy',
		'menu-item-status' => 'publish',
		'menu-item-parent-id' => $parent_id,
		'menu-item-attr-title' => $term->name,
		'menu-item-description' => $term->description,
		'menu-item-title' => $term->name,
		'menu-item-target' => '',
		'menu-item-classes' => 'termid-'.$term->term_id.' parentid-'.$parent_id,
		'menu-item-xfn' => '',
	);
	return wp_update_nav_menu_item( $menu_id, 0, $args );
}

/**
 * Returns the nav_menu_item ID of an item that has the term name
 *
 * @param   object    the parent nav_menu_item ID
 * @param   object    nav_menu_items
 * @return  boolean   returns true/false
 */
function wps_get_nav_menu_item_id( $term , $nav_menu_items ) {
	foreach ( $nav_menu_items as $nav_menu_item ) {
		if ( $term == $nav_menu_item->post_excerpt || $term == $nav_menu_item->post_title ) {
			return $nav_menu_item->ID;
		}
	}
	return false;
}

/**
 * Returns all child nav_menu_items under a specific parent
 *
 * @param   int       the parent nav_menu_item ID
 * @param   array     nav_menu_items
 * @return  array     returns filtered array of nav_menu_items
 */
function get_nav_menu_item_children( $parent_id, $nav_menu_items ) {
	$nav_menu_item_list = array();
	foreach ( (array) $nav_menu_items as $nav_menu_item ) {
		if ( $nav_menu_item->menu_item_parent == $parent_id ) {
			$nav_menu_item_list[] = $nav_menu_item;
			if ( $children = get_nav_menu_item_children( $nav_menu_item->ID, $nav_menu_items ) )
				$nav_menu_item_list = array_merge( $nav_menu_item_list, $children );
			}
	}
	return $nav_menu_item_list;
}

For use of get_nav_menu_item_children() see previous post: .