Menu item not created on theme activation

The value of $menu_id is not initialized if the menu already exists. So, if on theme activation, $menu_exists is true, $menu_id will never be set to a value and this line should produce a PHP warning:

$locations[$menulocation] = $menu_id;

You could try adding it like this:

if ( $menu_exists ) {
    $menu_id = $menu_exists->term_id;

} else {
    // Menu doesn't exist, let's create it.
    $menu_id = wp_create_nav_menu( $menu_name );

    wp_update_nav_menu_item( $menu_id, $new_page_id, array(
        'menu-item-title' =>  __( $new_page_title ),
        'menu-item-url' => home_url( $new_page_slug ),
        'menu-item-status' => 'publish' ) );
}

That may not fix your problem. I couldn’t test some things without knowing more about the theme settings.