Huge Menu doesn't accept changes

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

The post that helped me fix it: http://drupal.org/node/257108