Add this just below your support (or anywhere inside register_post_type array )
‘taxonomies’ => array(‘category’, ‘post_tag’).
And for 404 error, you miss to add flush_rewrite_rules();
So your final code should look like this
/**
add_action( 'init', 'create_post_type_othercities' );
function create_post_type_othercities() {
register_post_type( 'other-cities',
array(
'labels' => array(
'name' => __( 'Other Cities' ),
'singular_name' => __( 'City' )
),
'public' => true,
'has_archive' => true,
'capability_type' => 'post',
'publicly_queryable' => true,
'hierarchical' => true,
'show_ui' => true,
'supports' => array("title", "editor", "thumbnail", "author", "custom-fields", "excerpt", "comments"),
'taxonomies' => array('category', 'post_tag')
)
);
flush_rewrite_rules();
}
//Create taxonomy(category) for Other cities
register_taxonomy("other-cities", array("other-cities"), array("hierarchical" => true, "label" => "Cities", "singular_label" => "City", "rewrite" => true));
**/