Error “The given object ID is not that of a menu item” on menu with 40+ items

When ever I try to add menu items past about 40 I get an error “The given object ID is not that of a menu item” and many of my menu items will disappear from the menu at random.

The site I am working on has approx 65 pages in total but I am unable to get them all in because of this.

I am referring to the new WordPress menu management interface

The solution I found was to get in touch with my webhost and have them up the PHP memory limit on my account from 64MB to 128MB. The problem went away after that.