I cam across this thread recently as appear to be having the same issue when there are too many pages in the nav menu and one cannot save them.
http://wordpress.org/support/topic/rc32-menus-still-crippled?replies=28
Although it shows as resolved it does not look as though it has been. Whilst my site has a lot of pages in the menu it does not seem right that I can only go so far before it gives me the 500 server error.
I am on a big dedicated server and at first we increased the following:
suhosin.memory_limit 128M 128M
suhosin.post.max_value_length 65000 65000
suhosin.request.max_value_length 65000 65000
We then changed the limit to 256M but this still couldn't hack it. I also changed the wp config settings to include 128m to see if this would handle it but no joy.
I'm not currently looking for alternatives as I like the drag and drop feature, but would, and need to be able to add more sub pages to my current menu.
If anyone else knows what could be done it would be most appreciated