Theme Location empty

“The current theme does not natively support menus

This is your problem. Your Theme does not implement the core WordPress custom navigation menus feature.

The primary menu shows all the pages…

I assume that it is doing so via a call to wp_list_pages()

…and the secondary menu displays the categories by default.

I assume that it is doing so via a call to wp_list_categories().

How to fix

You will need to modify your Theme to accommodate the custom navigation menus feature. Fortunately, doing so is not hard at all. It involves two steps:

1. Registering Theme Locations for your custom nav menus
2. Outputting the custom nav menus in in the template

Registering Theme Locations

You register Theme Locations via register_nav_menus().

Add the following to functions.php, ideally within a setup function:

function wpse73875_setup_theme() {
    // Register nav menu Theme Locations
    register_nav_menus( array(
        'primary' => 'Primary Menu',
        'secondary' => 'Secondary Menu'
    ) );
}
add_action( 'after_setup_theme', 'wpse73875_setup_theme' );

Outputting custom nav menus in the template

You will need to find where your Theme calls wp_list_pages() and wp_list_categories(). You will probably find one or both in header.php. We’ll let both menus fallback to their current output (pages and categories), by wrapping our call to wp_nav_menu() inside a has_nav_menu() conditional.

Replace this:

wp_list_pages( /* there may or may not be args here */ );

… with this:

if ( has_nav_menu( 'primary' ) ) {
    wp_nav_menu( array(
        'theme_location' => 'primary'
    ) );
} else {
    wp_list_pages( /* exactly as it was in the Theme previously */ );
}

And replace this:

wp_list_categories( /* there may or may not be args here */ );

…with this:

if ( has_nav_menu( 'secondary' ) ) {
    wp_nav_menu( array(
        'theme_location' => 'secondary'
    ) );
} else {
    wp_list_categories( /* exactly as it was in the Theme previously */ );
}

You may need to play around with the arguments passed to wp_nav_menu() in each case. Have a look at the Codex entry for more information.

For more precise instructions

For more precise instructions on converting your specific Theme’s menus to support custom nav menus, you’ll need to update your question to include the exact code that calls wp_list_pages() and wp_list_categories().