To mitigate denial of service attacks, PHP 5.3.9 introduced a max-input-vars configuration that defaults to 1000. This has also been backported to some 5.2.x security builds bundled with Ubuntu and other major Linux distributions.
Each menu item on the admin/structure/menu/manage/MENU_NAME form adds several POST variables of the form
max-input-vars value applies to each level in a multidimensional array, not to the total number of variables, so even though several subvariables within the square brackets are posted, each menu item counts as just one variable against the 1000 limit. Still, for sites with >1000 items in a menu, this results in a broken administration page.
A possible fix is to group the submitted data into partitioned subarrays, so that no single array exceeds 1000.