I’ve tested your code and it works perfectly if you register the post type in the init action hook. In your code I don’t see the action hook where you register the post type. Cna you try this? (remember to flush rewirte rules after update the code. Note that I remove the undefined variable $labels in the $args array for taxonomies):
add_action('init', 'cyb_register_post_type_and_taxonomies');
function cyb_register_post_type_and_taxonomies() {
register_post_type( 'city',
array(
'labels' =>
array(
'name' => 'City Guides',
'singular_name' => 'City Guides',
'add_new' => 'Add New',
'add_new_item' => 'Add New retailer',
'edit' => 'Edit',
'edit_item' => 'Edit retailer',
'new_item' => 'New retailer',
'view' => 'View',
'view_item' => 'View retailer',
'search_items' => 'Search retailers',
'not_found' => 'No retailer found',
'not_found_in_trash' => 'No Shop retailer in Trash',
'parent' => 'Parent retailer'
),
'public' => true,
'menu_position' => 6,
'supports' => array( 'title', 'editor', 'thumbnail' ),
'has_archive' => true,
'taxonomies' => array('city_categories'),
'can_export' => true,
'rewrite' => array('slug'=>'travel')
)
);
$args = array(
'labels' => array(),
'public' => true,
'show_in_nav_menus' => true,
'show_ui' => true,
'show_tagcloud' => true,
'show_admin_column' => true,
'hierarchical' => true,
'rewrite' => true,
'query_var' => true
);
register_taxonomy( 'city_categories', array('city'), $args );
$args = array(
'labels' => array(), // defined correctly, shortened the code
'public' => true,
'show_in_nav_menus' => true,
'show_ui' => true,
'show_tagcloud' => true,
'show_admin_column' => true,
'hierarchical' => true,
'rewrite' => true,
'query_var' => true,
'sort' => true
);
register_taxonomy( 'cities', array('city'), $args );
}