On a fresh, no demo install (nothing checked during Kickstart), when I add / delete taxonomy terms in the only available taxonomy vocabulary, nothing happens to the menu.
I'm trying to write a documentation page on recreating the catalog from scratch, or at least using what we have. So I'm going to recommend in the documentation page that the user fix it the way I fixed it:
1) Go here: admin/structure/taxonomy/product_category/edit
2) Select the checkbox "Select to rebuild the menu on submit."
3) Click "save"
Is there any way we could spare the site builders this step?