@Scribu, thanks for this plugin.
I still think that the this should be the default UI behavior, even if having a lo of categories but a lot of sub-categories, too - it very confuses as one just can't know which category is child of who, especially if there are some children or grand-children categories, with the same name....
I hope that #3130 enhancement idea will go to the core. Do you know if there are plans to put such a feature in the core?
http://wordpress.org/extend/plugins/category-checklist-tree/