Inserting terms in an Hierarchical Taxonomy
The hierarchy is cached and it’s not invalidated properly. This is a bug, still unresolved as of WP 3.1. A workaround would be to call delete_option(“{$taxonomy}_children”); directly. See the _get_term_hierarchy() function.