My Apache error logs have nothing. The access log shows the 500 error, but nothing useful. I didn't have the issue with 3.4. I haven't made any changes since then that I can think of that would be causing the issue other than upgrading WordPress to 3.4.1 and upgrading my Suffusion theme to 4.2.4.
PHP isn't running out of memory or logging any errors. I've also tried restarting Apache and PHP to it had plenty of memory. It isn't a timeout as I get the 500 error right after I hit the save button.
"POST /wp-admin/nav-menus.php HTTP/1.1" 500 589 "http://blindscribblings.com/wp-admin/nav-menus.php
This is a production site that people are hitting. Disabling all plugins isn't practical and would break more functionality on the site.