It looks like the "menu" package which includes "update-menus"
is only suggested, at least in r14 Wheezy.

Is there some other mechanism that is supposed to be
updating menus when TDE packages are installed?

If not, I would suggest that something - perhaps "kicker-trinity"
should have a hard dependency on "menu".

--Mike