Wordpress - How do I add a custom taxonomy as an option for menus under "Appearance" > "Menus"

Check "Screen options" on the "Menu" page. That worked for me.

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