Tipos de posts personalizados, taxonomías y enlaces permanentes

Esto me está volviendo loco y estoy seguro de que es simple, pero nada de lo que busco muestra una estructura simple (todo es muy complejo).

Tengo un tipo de post personalizado product_listing y una taxonomía personalizada product_cat (que es jerárquica y debe comportarse como categorías).

Simplemente quiero que mis URLs se vean así:

mysite.com/products/category1/product-name1 
mysite.com/products/category2/product-name2

Pero por más que lo intento, sigo obteniendo el temido error 404. Las páginas funcionan bien y los Posts funcionan bien, pero mis posts personalizados no funcionan correctamente. Se están mostrando como:

mysite.com/products/product-name1
mysite.com/products/product-name2

¡Lo cual realmente funciona! Es solo que quiero ver mi taxonomía personalizada allí y además quiero poder acceder a la plantilla taxonomy.php que tengo configurada yendo a:

mysite.com/products/category1/
mysite.com/products/category2/

Ninguno de mis slugs es igual, ni quiero que lo sean. Aquí está la parte del tipo de post y taxonomía de mi archivo functions.php:

///// TIPOS DE POST PERSONALIZADOS /////

// registrar el nuevo tipo de post
register_post_type( 'product_listing', array( 
    'labels'                 => array(
        'name'               => __( 'Productos' ),
        'singular_name'      => __( 'Producto' ),
        'add_new'            => __( 'Añadir Nuevo' ),
        'add_new_item'       => __( 'Crear Nuevo Producto' ),
        'edit'               => __( 'Editar' ),
        'edit_item'          => __( 'Editar Producto' ),
        'new_item'           => __( 'Nuevo Producto' ),
        'view'               => __( 'Ver Productos' ),
        'view_item'          => __( 'Ver Producto' ),
        'search_items'       => __( 'Buscar Productos' ),
        'not_found'          => __( 'No se encontraron productos' ),
        'not_found_in_trash' => __( 'No se encontraron productos en la papelera' ),
        'parent'             => __( 'Producto Padre' ),
    ),
    'description'           => __( 'Aquí es donde puedes crear nuevos productos en tu sitio.' ),
    'public'                => true,
    'show_ui'               => true,
    'capability_type'       => 'post',
    'publicly_queryable'    => true,
    'exclude_from_search'   => false,
    'menu_position'         => 2,
    'menu_icon'             => get_stylesheet_directory_uri() . '/images/tag_orange.png',
    'hierarchical'          => true,
    '_builtin'              => false, // ¡Es un tipo de post personalizado, no integrado!
    'rewrite'               => array( 'slug' => 'products', 'with_front' => true ),
    'query_var'             => true,
    'supports'              => array( 'title', 'editor', 'author', 'thumbnail', 'excerpt', 'trackbacks', 'custom-fields', 'comments', 'revisions' ),
) );


//conectar a la acción init y llamar a create_book_taxonomies cuando se active
add_action( 'init', 'create_product_taxonomies', 0 );
//add_action('admin_init', 'flush_rewrite_rules');

//crear dos taxonomías, géneros y escritores para el tipo de post "book"
function create_product_taxonomies() {
    // Agregar nueva taxonomía, hacerla jerárquica (como categorías)
    $labels = array(
        'name'              => _x( 'Categorías', 'nombre general de taxonomía' ),
        'singular_name'     => _x( 'Categoría', 'nombre singular de taxonomía' ),
        'search_items'      =>  __( 'Buscar Categorías' ),
        'all_items'         => __( 'Todas las Categorías' ),
        'parent_item'       => __( 'Categorías Padre' ),
        'parent_item_colon' => __( 'Categorías Padre:' ),
        'edit_item'         => __( 'Editar Categoría' ), 
        'update_item'       => __( 'Actualizar Categoría' ),
        'add_new_item'      => __( 'Añadir Nueva Categoría' ),
        'new_item_name'     => __( 'Nuevo Nombre de Categoría' ),
        'menu_name'         => __( 'Categoría' ),
    );  

    register_taxonomy( 'product_cat', array( 'product_listing' ), array(
        'hierarchical'  => true,
        'labels'        => $labels,
        'show_ui'       => true,
        'query_var'     => true,
        //'rewrite'     => true,
        'rewrite'       => array( 'slug' => '%category%', 'with_front' => true ),
    ) );

    // Agregar nueva taxonomía, NO jerárquica (como etiquetas)
    $labels = array(
        'name'                       => _x( 'Aromas', 'nombre general de taxonomía' ),
        'singular_name'              => _x( 'Aroma', 'nombre singular de taxonomía' ),
        'search_items'               =>  __( 'Buscar Aromas' ),
        'popular_items'              => __( 'Aromas Populares' ),
        'all_items'                  => __( 'Todos los Aromas' ),
        'parent_item'                => null,
        'parent_item_colon'          => null,
        'edit_item'                  => __( 'Editar Aroma' ), 
        'update_item'                => __( 'Actualizar Aroma' ),
        'add_new_item'               => __( 'Añadir Nuevo Aroma' ),
        'new_item_name'              => __( 'Nuevo Nombre de Aroma' ),
        'separate_items_with_commas' => __( 'Separar aromas con comas' ),
        'add_or_remove_items'        => __( 'Añadir o eliminar aromas' ),
        'choose_from_most_used'      => __( 'Elegir entre los aromas más usados' ),
        'menu_name'                  => __( 'Aromas' ),
    ); 

    register_taxonomy( 'scent', 'product_listing', array(
        'hierarchical'  => false,
        'labels'        => $labels,
        'show_ui'       => true,
        'query_var'     => true,
        //'rewrite'     => array( 'slug' => 'scents' ),
    ) );
}

También tengo otra taxonomía personalizada de scents que idealmente me gustaría que tuviera algún tipo de url amigable, pero soy más flexible en esto. Me gustaría poder acceder a una lista de todos los aromas yendo a mysite.com/products/scents pero no tienen que ser específicos de la categoría.

¿Alguien puede ayudarme?