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