Here's an odd one for you. I can't put more than 90 items in a menu. The 91st will delete the last item in the menu.
Every issue seems to point to changing two values on your site, see here - http://wordpress.org/support/topic/the-menu-has-a-limit-of-49-links-of-pages-in-the-navbar
However, "suhosin" is disabled on my server, so don't have any