The only reference I can find to this menu problem is in Trac #14134 where the 16 menu object limit was due to suhosin. http://core.trac.wordpress.org/ticket/14134
Since it is my server I have tweaked suhosin and memory limits to stupidly high levels but still get the same behavior of only 16 menu items - anything after that gets dropped and the last item in the menu gets switched to custom, whether it was a category or page.Makes me wonder if the limit is actually fifteen and a half :)
suhosin.request.max_value_length = 999999
suhosin.post.max_value_length = 999999
suhosin.request.max_vars = 999999
suhosin.post.max_vars = 999999
suhosin.request.max_varname_length = 256
suhosin.request.max_totalname_length = 1024
suhosin.request.max_array_depth = 200
Confirmed these configurations are being registered by checking phpinfo and everything is as entered above. Problem exists on other WP installs on this server.
Tried disabling plugins just in case and did a trace through the WP code confirming that the number of items in the POST array are never more than 16, also restarted the server, waved the dead chicken and turned around three times... no luck.