Wordpress - Large WP 3.0 menu times out and won't save

You can always try to split your menu into 2 separate menus and then just display them next to each other in your theme. It's far from perfect and doesn't help a bit in understanding the root of your problem but it could help.

You can use it as temporary workaround to GTD before deadline and then dig deep into memory issues or whatever causes your trouble...