Executing a noble should have severe relations impact (as it does) on all nobles, but execution of insurrection leaders should actually lead to an increase in relations much as taking out a bandit hideout has a positive impact on nearby nobles. These are rebels against the lawful authority who have committed crimes against the sovereignty in power need to be made an example of quickly before others think they can become kings themselves merely by rousing mobs to begin to burn and loot cities. It makes no sense that nobles would be upset by this, even your enemies.