Can't rearrange menu items on Drupal 6
PHP 5.3 enforces a max_input_vars (see the accepted answer in PHP Warning: Unknown: Input variables exceeded 1000) and I've seen it create similar errors (page saves yet nothing is saved) when setting permissions for users on sites where there are lots of permissions and lots of roles, so, most probably the same is happening here with the menu UI when it has lots of menu items.  To resolve it, bump up the value on your system (see php.net documentation for max_input_vars) until things work again.