If you have the menu properly applied to a template page then there should be no need to update any of the individual instances on any other page, in fact you should not be able to make edits to these other menus if it was applied in the template properly. In the template you must have the menu in a common area, not an editable region. If it is inside of an editable region the code will not properly propagate to the other pages that are derived from this template. If done correctly you should not need to adjust the links to any of the other pages. Please let me know if you continue to have any problems with this so we can look into this further.