Functionally, this is an impossibility due to the present native structure of the database. I was hoping for feasability too, but I just found a workaround, based on how I structured my architecture. I'd suggest using tags, instead. Long story short, each category is a node in a Tree Data Structure with a pointer to its parent, but no pointers to children. This is for simplicity and ease of use. If they were to also store pointers to children, and modify the structure to permit multiple parents, the structure would become (I believe) exponentially more complicated, and hamper further development on more critical areas.
For the technical details of how WordPress stores Categories, read on ... for the sake of brevity and clarity, I'll omit a few columns from a few tables, that didn't seem relevant.
Categories are stored in the WordPress Database across three tables, wp_terms wp_term_taxonomy and wp_term_relationships iirc. wp_terms stores a term_id, term_name, and term_slug. term_id is auto-incrementing, so the code starts by shoving the name and slug into the wp_terms table, and then fetching the ID at which it was inserted. Name doesn't have to be unique, but slug does!
Then we move onto the wp_term_taxonomy table. As you may have noticed, we've been inserting words, but never saying what they meant! The wp_term_taxonomy table stores term_taxonomy_id, term_id, taxonomy, description, parent, and count. Now, count simply stores (for category purposes) the number of events that are assigned to that category, ignoring child-categories. We can ignore it.
term_taxonomy_id is the auto incrementing id that bumps up whenever you add in a new taxonomy. term_id is the term in question from the wp_terms table. Notice that this table has no slot for name. It simply links into the wp_terms table, so you can have multiple term_taxonomies, pulling from the same name in wp_terms. taxonomy is what the term is to be considered. For our purposes, it will always be 'category'. description is the description of the category, and parent is an INT, containing the parent category (that really cool thing that we care about).
wp_term_relationships is simply tying wp_term_taxonomy in with actual object_ids (posts, etc.) It's the link between a post and its category, allowing you to create multiple entries, to link one post to multiple categories (because the link is stored seperately from either the parent or child).
Now, the significance of all this. Categories are built as a tree data structure. Each category is a very simple construct, storing a payload and a pointer -- the normal, lightest way to build trees. Parents don't have pointers to their children, that could have to store anywhere from {no values} up to {thousands} or more. Instead, each category just stores (data) (parent) and you can travel up and down the tree. To travel to a parent, simply follow the pointer! To travel back down, it becomes a bit more cumbersome, as you have to scan the entire table for any elements that have the parent assigned as a parent -- fortunately, an easy task with a MySQL database, simply querying SELECT * FROMwp_term_taxonomy WHERE parent = '{$term_taxonomy}', where $term_taxonomy is the term_taxonomy of the parent in question!
Long story short, use tags, because a plugin would have to rewrite the whole system, which is possible, but not very cost-effective!
Mark 
Binh WPO 
Henry 
