I found a fairly painless way to order categories that doesn't require any code mods. First create a column called "cat_order" in the wp_categories table. I made mine varchar(64). Then put numbers or whatever you want in the field for each category using phpMyAdmin or other DB software. Then use "sort_column=order" in the call to wp_list_cats (or put "order" in the sort_column parameter of list_cats). There's no way to edit the order through WordPress unless you modify the admin scripts.
Getting the hierarchical display of categories working was a whole nother hassle. list_cats has some serious bugs.