Unusable menus and “Illegal widget setting ID: nav_menu_item[]” error

I had the same problem. I did not have pre-existing menus, but newly created ones had the same symptoms as you described.

In my case, the problem was a ill-defined table wp_terms. It was missing the AUTO_INCREMENT flag on the column term_id as well as all indexes and the primary key.

I can only assume that the update process messed up at some point in the past. I run a pretty ancient installation which was originally set up in 2005.

The following change fixed the problem for me:

ALTER TABLE `wp_terms`
CHANGE COLUMN `term_id` `term_id` BIGINT(20) UNSIGNED NOT NULL AUTO_INCREMENT FIRST,
ADD PRIMARY KEY (`term_id`),
ADD INDEX `name` (`name`),
ADD INDEX `slug` (`slug`);

I would recommend comparing your schema against a current schema though. wp_term_taxonomy might be involved as well (wasn’t in my case).