Your custom taxonomy should show up as an option for custom menus, if you have
'show_in_nav_menus' => true
as a parameter when you register your post type with register_post_type(). You can check all the available parameters in the codex entry http://codex.wordpress.org/Function_Reference/register_post_type#Arguments