All henchmen of da boss - Stomper Kreeg, all three of da Guards, Captain Kromcrush, and da Observer - give tribute to da new boss.  If you kill a henchman, then that henchman can't give tribute!  Each one you keep alive will give you more tribute.  Keep all of them alive and you get da BIG tribute!$B$BYeah!