yes your solution worked Ale thanks. 🙂
exactly same problem is happening to me with word press version 4.4. What actually happening here is that after saving newly created menu. If suppose I later try to edit or add new menu item to existing menu I cant see the existing menu items in menu list. They still exist in database as I can see them in user end but I cant edit them as they are no more visible
See Img Here : http://imgur.com/VlSwBkl
I had around 350 Entries in my tables and I was having exactly same error. After reading your comments about possibly shortage of memory on server as cause for the error I thought to delete few unimportant rows entries (May be 10 or 12 I deleted) and then I tried to save table again.. and wolla !! It saved successfully