Hi Todd,
The taxonomy terms are requested from WordPress via the get_terms() call when the plugin is showing them, so only existing terms can show up. That means, that the terms may still exist, or the page contaning the search is still cached at some layer, and serving the old layout.
I suggest trying the preview window on the plugin back-end, if it still displays the taxonomy terms there, that means they still exist, if not, then it’s only a cache related problem on the front-end.