With many items in the Gradebook, it can be difficult to efficiently sort items. There should be a "Sort" popup window where instructors can see their gradebook items and categories in a vertical list. Everything in this list can be dragged and dropped into new locations.
When changing items from uncategorized to categorized, item settings like "include in course grade calculation" and "release to students" need to be updated appropriately.
The sort order should also respect whatever view you were currently using in the Gradebook. So if you were viewing items by category, the sort box will be categorized. If you were viewing your Gradebook not grouped by category, the sort box would reflect the uncategorized sort order.