The problem was that my host had a limit of 200 variables per post,
and long menus with more variables were being rejected. The same started
happening on the Permissions page, since I had a lot of roles and
content types.
I bumped up suhosin.post.max_vars and suhosin.request.max_vars from 200 to 2048 on the server, and now it works.
If your host doesn't have a control panel where you can do this, add the following to your php.ini:
suhosin.post.max_vars = 2048
suhosin.request.max_vars = 2048