Hello, @Dwilo
I have checked your site and don’t see any other issues that could cause this problem. If I create smaller menu then everything works fine, so, the only reason that may affect it is max input vars limit. Does your server run Suhosin? Have you changed Suhosin directives if your server runs it?
Here you can find detailed explanation about this issue http://sevenspark.com/wordpress/menu-item-limit
Regards