When you change a sort index or a name of a page, it gets changed in the admin tree, but it doesn't get changed to the user straight away.
It seems that Epi is caching the menu structure, and the only way to get the latest version to the user is to restart the appPool in IIS.
is this a bug or is there a way around it?
I would say By design.
But you could try use EPiServer.DataFactoryCache.RemoveListing(PageReference pagelink) to refresh the tree.
Haven't tested it myself.