I was told refreshing SPNavigation might help with my missing and not-updating bredacrumb issue from this post. How do I force SPNavigation to refresh?
I had that problem working with a usercontrol that displayed elements retrieved from the QuickLaunch navigation. When I added or renamed elements, the changes were not reflected in the control until I removed the "Sort Automatically" and moved an element from its original position. Sounded to me like there was some kind of caching going on, although not really sure what the rules are for refreshing.
So I would try following these steps:
Site Settings -> Look and Feel -> Navigation -> Select Sort Manually -> Change the order of the items in the navigation -> OK