Menu Structure with Links failure to update

Did you actually create a specific menu and link it to one position you defined in functions.php? Once you do not link it to a position, WordPress grabs all pages and puts it in a menu.

You should go like this:

1.) You put something this in the functions.php of your theme in order to register menues (if you only need one, leave out the line with the ‘footer’ menu):

function register_my_menus() {
register_nav_menus(
array(
'nav' => 'Main',
'footer' => 'Footer' )
);
}
add_action( 'init', 'register_my_menus' );

2.) You then determine where this should appear in your template, e.g. header.php, just like this:
<?php wp_nav_menu( array('menu' => 'nav' )); ?>

3.) Last but not least you create your menu and give it the position needed (i.e. ‘Main’) in my example.

The menu should then update normally. If you use a ready-made theme you might just have to check for the right position to pick in the menu editing window?