You probably edited the navigation menu directly on that certain page, rather than making that navigation menu change on the design template. If you make the change on the Template and then follow the steps to save and republish, the navigation menu changes will appear on all pages assigned to that template.
Or, you might have two or more different templates assigned to different pages. Check the Assign a template to a page to see what template names are specified for each page.