Error 500 – when revising and saving navigation menu

Recently I started getting an error message whenever I added a page to my navigation menu. It actually worked OK, so I could ignore the message and move along, but tonight I can’t make any changes to the menu structure. I get this error message consistently, and I’m unable to add any new pages to the menu:

Error 500 – Internal server error
An internal server error has occured!
Please try again later.

I installed a plugin to monitor memory usage, and it says I’m using 21 mb and have 64 mb available, so I don’t think that’s the problem. I tried disabling all plugins, and the same error persisted. I am running the latest WP 3.1.2 with Atahualpa 3.6.4.

I would be most grateful if anyone had any advice for me on how to fix this problem.