New category does not show up in term_data table

I use CCK content types as categories. If I create a new category it doesn't show up in the taxonomy tables (at least in the term_data table). Only after editing the term (category node) for the second time the table gets updated.

I think the Category module had similar bug few months ago but I do not remember what the fix was.
I tried to reinstall the category module but the bug remains.

Since one of my sites which is using direct sql queries from the taxonomy tables is completely broken because of this bug I set the priority critical.