You have to find the ceremonial axe and put it on the proper one. Not just any axe will do.

If you've already tried that, I'm not sure what the issue is. It worked for me.