Show Different Custom Menu on Different Category Pages

Add a new menu called category-menu:

if( function_exists( "wp_nav_menu' ) ) 
{
    add_theme_support( 'nav-menus' );

    register_nav_menus( array( 
        'primary-menu' => __( 'Primary Menu', 'woothemes' ) 
    ));

    register_nav_menus( array( 
        'top-menu' => __( 'Top Menu', 'woothemes' ) 
    ));

    register_nav_menus( array( 
        'category-menu' => __( 'Category Menu', 'woothemes' ) 
    ));
}

And output it with the conditional is_category():

if( function_exists( 'has_nav_menu' ) && has_nav_menu( 'primary-menu' ) ) 
{
    // On category 'Cheese'
    if( is_category( 'Cheese' ) )
    {
        echo '<h3>' . woo_get_menu_name( 'category-menu' ) . '</h3>';

        wp_nav_menu( array( 
            'sort_column'    => 'menu_order', 
            'container'      => 'ul', 
            'menu_id'        => 'main-nav', 
            'menu_class'     => 'nav fl', 
            'theme_location' => 'category-menu' 
        ));
    }
    else
    {
        echo '<h3>' . woo_get_menu_name( 'primary-menu' ) . '</h3>';

        wp_nav_menu( array( 
            'sort_column'    => 'menu_order', 
            'container'      => 'ul', 
            'menu_id'        => 'main-nav', 
            'menu_class'     => 'nav fl', 
            'theme_location' => 'primary-menu' 
        ));
    }
}