My site doesn't use categories apart from a default "News" category. Instead, I use a custom field for "Country" (i.e., country of publication). Why? Because potentially I'd need to use a hundred or more categories and (even if the Create New Post layout could handle that, picking from a huge list would just slow things down too much. It's far easier for me to type into a custom field than select from a long list.
So...my suggestion is this: for people like me who are jury-rigging "categories" with custom fields, why not provide an alternate method of selecting a category such as a simple field which could be typed into or entered with a keyboard macro?