Hi Andy,
I confirm Wei Li's diagnosis, you may think you have file permissions correct but this problem is definitely caused by incorrect file system permissions.
What happens is that the SiteMap which is the data source for the menus is cached. To clear the cache it needs to touch the cache dependency files located under /Data/Sites/[SiteID]/systemfiles (where [SiteID] is typically 1 in a single site installation).
If the folder is not writable it cannot modify these files so the cache does not get cleared as it should when you create or delete a page.
If you moved the site from one machine to another, it is possible files there have funky permissions on them, so even if the folder permissions are correct the existing files may have bad permissions. Try deleting all files from /Data/Sites/1/systemfiles, if the folder permissions are correct the files will be re-created as needed. If the files do not come back on their own then it means the folder permissions are not correct, it cannot write files there.
Hope it helps,
Joe