Suggest to use Menu manager->Rebuild to repair a corrupt menu structure. Also investigate where the corruption comes from. Haven't found it in a clean install, nor update. Try a normal install when suspecting Softaculous.

moving to information required

I just installed 3.3.6 using softaculous on siteground.com - no problems

Rebuild didn't normalize the lft/rgt columns. I created lots of menus and was changing the positions of them many times. Even used 'batch' moving too. It will be lots of work to recreate what I have now and reinstalling. For now I don't normally touch any data inside the MySQL database. Not sure the exact functionality or lft & rgt and if anyone is familiar with it and can confirm with moving a bunch of items around if the numbering scheme is working correct. Thanks.

Just a note too: The warning aren't very informative. For example possibly still part of the same coding section, The original warning "Save failed with the following error:" had no error after the colon.

Later in the day after fixing the lft & rgt values, I was doing more changes to the menu system I had also got a different warning "Batch process failed with following error: Another menu item with the same parent has this alias" but trying to find which alias is duplicated is a bit of work.

The error message fixes aren't urgent just the 'possible' problem that lead to my menu getting to a point of not being able to save changes.

Setting the prio to medium because the problem can't be reproduced

A user of my extension has the same similar issue, with articles, categories, contact... all core and third parties components...
Menu item saving for this user is working.
I don't know where the issue could come from, but for this user, it's not in Joomla 3, but 2.5.28...

When error reporting on, in already article saving, i've got this notice :
Strict Standards: Declaration of JParameter::loadSetupFile() should be compatible with that of JRegistry::loadSetupFile() in /***/libraries/joomla/html/parameter.php on line 512
Don't know if it could be a similar issue with the one of this issue on j3 here...?!?...

If i find where the problem is, i will inform you...
Cyril

After considerable time without update or further information I am closing this - it can always be re-opened

I have encountered this problem as well, as did the client and previous developer back in March. It is very persistent and the menu item ordering is extremely fragile. Both the front and backend display the menu items in the incorrect order, even though their parent's are set correctly. Rebuilding the menu fails, copying menu items fails. I can save the menu items sometimes and not others, and I have also seen a negative value in the rgt column of the menu table. Updating to 3.4.3 and rebuilding the cache didn't throw any errors but it didn't solve the problem either. It is failing on Ubuntu locally and CentOS on the live production server.

The notes above mention a need for additional information. I would be happy to provide whatever you need to resolve this issue. My temporary workaround for the frontend output (because the site is already live) has been to write a custom module that uses a basic query for selecting and ordering the menu items, and a recursive function to output the links in the same unordered list.