Yeah, there's a lot of Brutalities that just plain don't work, or only work on very rare occasions.

When you have trouble with a Brutality like that, I recommend making sure that you try to chain the attack into a combo that will continue past "Finish Him" and then activate the attack during that combo. That usually seems to work. You may also be trying to do it too early (i.e. the opponent still has too much health)