Is there any more information you can provide us?
ExpressionEngine version, any other extensions that modify or add to the Publish interface, etc?
Or anything out of the ordinary from a “usual” EE install?
Thanks to the magic of computers, this bug has somehow disappeared. (The screenshot shows I’m not crazy...)
All I can think is that I switched the category list from custom to alphabetical a few times back and forth. Maybe one of those times reset the ordering counter.