Looks like a side effect of the scripting capabilities being turned off in your tenant.
Whenever you create a new tenant, the custom scripting capabilities are turned off by default. Now, it appears that even to change the Navigation, from say Structural navigation to managed navigation, or for any other changes in Navigation settings we need to enable the custom scripting capabilities.
You can lookup at the links mentioned below:
Confusing Access Denied and managing Navigation Office 365
Allow or prevent custom script
Now, to fix this issue, you need SharePoint admin rights.
After that, you can follow the steps mentioned below:
Option 1 - Using admin center UI
1) Go to the admin center. URL would be like -
2) Click on settings
3) In the settings page, in the
Custom Script section, set the values to allow as in below image:
4) Click on OK to save the settings.
Now, you need to wait 24 hours for the scripting capabilities to be enabled. After that is turned on, you will be able to save the settings.
Option 2 : - Using SharePoint Online PowerShell
After opening the SPO PowerShell, run the below commands:
Connect-SPOService -Url "https://tenantname-admin.sharepoint.com"
Set-SPOSite "https://tenantname.sharepoint.com/sites/test" -DenyAddAndCustomizePages 0
Once you have executed these commands, it will be reflected immediately and you dont need to wait for 24 hours.
Download link - SPO PowerShell
PS - You require SharePoint admin credentials for the above mentioned steps. Site Collection admin wont work.