The lower half looks great, trouble is the top.
He looks like hes pushing a baby stroller, ready to do a very cliche karate chop.
I recommend he have his hands in the ready position to either draw a weapon, or attack with a weapon.
This is a piss poor edit but I hope it gives you some idea of what I mean:
*EDIT* Re-reading your post about the leg timing:
Watching it at a slower speed shows the left foot ( his left ) snaps straight down to the ground on frame 3. The thigh also seems shorter then it should be when it lifts up, which gives it the impression he is spreading his legs, an odd way to run for sure.
On frame 9, the right foot ( his right ) has the same problem where it snaps straight to the ground.
Overall the legs suffer from some unevenness in their animation. I recommend you slow the animation down and watch it since the flaws are easier to see that way.
This has some killer potential for sure, it already looks great, once you fix the flaws it should look AwEsOmE