I asked the same question a while ago. Scribu gave me an answer here.
The long and short of it: after you insert your terms, add this line of code.
delete_option("my_custom_taxonomy_children");
Of course, replace my_custom_taxonomy with your own, but leave the _children part.