I am using the Appearance Menus editor (werrry naisse).
I have a big, honkin' menu, and I'm using the rather piggy Suffusion theme.
Whenever I submit a menu, it takes forever and a day, and ends with the following message splashed across the top of the screen:
"Request-URI Too Large
The requested URL's length exceeds the capacity limit for this server."
That tells me that GET is being used, when POST should be used. I know, because the exact same thing happened when I was designing my plugin.
Now, this may well be a Suffusion issue, but it may also be a WP issue.