I found this message from Mark Jaquith, WP lead developer:
The WordPress core team is quite aware of this issue, and it is
absolutely something that needs to be solved. It is an issue with how
the menus are saved. Too much data is passed back. It takes a lot of
memory and computation time, and many servers are configured to have
limits on the number of vars you can POST in one request.
Unfortunately, we just couldn’t reach a consensus on the best way to
solve it in time for WordPress 3.2. So for this release, it will have
to remain a known issue that menu saving performance degrades or
generates errors beyond a certain point (which may vary from server to
server).The Trac ticket has been tagged as 3.3-early, which means we’ll put it
as high priority early in the 3.3 development cycle.I appreciate your feedback and for holding us to a high standard! This
is how things get better.
The question is, when will t his be fixed? :-/