if you edit a menu and get a 500 or 404 and also see something like
max_input_vars limit too low.
edit your php.ini and adjust or add
max_input_vars = 5000
then restart Apache.
Oh yeah this is due to the limit on menu items php imposes on wp.
Other factors round this issue were a messy htaccess file and also permalinks, so check that too.