update-menus
será chamado assim mesmo, pois menu
registra o mesmo interesse que você. Você só precisa garantir que o gatilho seja executado primeiro. Triggers obedecem a ordenação de dependência, então um Enhances: menu
no seu arquivo de controle de pacotes (ou um Recommends: na outra direção) pode fazer o truque.