Can't add more categories in my menu (twenty eleven child)

Hi,
I’m running a small gaming blog at scanlines16.com and since my host provider moved to PHP 5.3 I’m having a strange issue with the menu. My blog runs with a custom child theme of Twenty Eleven.

I need to add a LOT of categories inside of my “collection” menu (up to 4 levels down) but it seems that after a certain number of entry (around 90) I simply can’t add anything anymore to the menu, pressing “Save Menu” doesn’t do anything. I can see all the entries in the database but they simply won’t show in the menu after a certain quantity.

I’m using the latest version of a plugin called “Types” which worked perfectly fine on the old server. That’s to handle custom types and taxonomies for the Collection menu because it uses separated categories from the rest of the blog.
[url=https://postimage.org/image/umm07jgdh/][img]https://s18.postimage.org/umm07jgdh/menu.jpg[/img][/url]

Here’s what I tried so far :

1) Deactivating all plugins (appart from Types) and rebuild the menu from scratch -> still the same issue

2) Checked that the server has enough memory (php config says :

Resource Limits memory_limit Maximum amount of memory a script may consume (32MB) 256M

3) raised memory useage of WP with

define(‘WP_MEMORY_LIMIT’, ‘128M’);

Any idea what might be causing all the trouble ? Do you belive it’s wp related or server side ? I’m open to any suggestions.

Thanks ??

[ Please do not bump, that’s not permitted here. ]