Some users of WordPress 3.0+ have a problem saving menus with more than 16 items. No error is displayed, but some menu items are missing when the menu is saved. If this is happening to you, your web server may have the Suhosin Hardening-Patch or Suhosin Extension for PHP installed.
Suhosin is an advanced protection system for PHP installations. It was designed to protect servers and users from known and unknown flaws in PHP applications and the PHP core. Suhosin comes in two independent parts, that can be used separately or in combination. The first part is a small patch against the PHP core, that implements a few low-level protections against bufferoverflows or format string vulnerabilities and the second part is a powerful PHP extension that implements all the other protections.
The (probable) reason for this is that your suhosin.post.max_vars and suhosin.request.max_vars options are set too low. Ask your host to increase the values on these options.
If you host the website yourself, you’ll need to edit your php.ini file (located in /etc/php5/apache2/php.ini on Debian Linux servers). Simply add these lines to the bottom of your php.ini:
suhosin.post.max_vars = 5000
suhosin.request.max_vars = 5000
And voila, you should be able to save menus with more than 16 items!