As MysteryMeat said, when walking or running your legs swing like a pendulum back and forth. Also try to make his body move with his legs, so not only his arms move, but his shoulders and head as well. This makes him look really 3D.

I made a little edit to show this the pendulum motion.

Wow, the shifting is weight is really cool, this is definitely something i'll keep in mind. I also  see that the motion blur solves the issue I had with the arms a lot.

edit:


An important part of picking colours you forgot is Hue-shifting, this makes especially the cloth look very bland. For clusters, try to make them as blocky as possible. You can see I tried adding a nose to his face as well, just to give him a bit more detail.

Edit:


I only changed the the movement of the axe, so please don't pay attention to his body. So you can clearly see I added smears, they may be too much but they clearly convey the movement. In your animation I thought that the swing upwards was the slash, only after studying it a bit I find out he was slamming it down actually. This is where your amount of  frames is imporant. Since the axe is heavy you need lots of frames where he brings the axe up and a pause  and overshoot when the axe is at its highest point. Then comes the swing and this is the place where you would actually use a smear and I suggest you use one. Also you want to have the impact frames be long to really slow how heavy the axe is again.