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.