Creating and editing large menus can often cause an error whereby the menu location will no longer save and neither can add a new menu item and save the menu to reflect this.
Please contact your host and ask them to report back to you the server php.ini `max_input_vars` settings. This should be increased if it set to `1000` or less. Typically increasing this setting to `3000` will resolve the issue.