When changing the Title or NavigationTitle fields of a page and publishing it to Experience Edge, the corresponding value in the Navigation rendering on other pages might not be updated.
To avoid the issue, pages and/or partial designs that have the Navigation rendering on their layout need to be republished. This can either be done individually or by selecting the Republish and Publish related items options when publishing the updated page.