(quick critique - I'm on the road)
I can't use Maya on my laptop here (I'm not at home), so I can't check your file. But judging by the clip it looks like there is a looping problem. Usually in a cycle your first and last frame are the same, so when you playblast the movie, you need to cut off the last frame. For example, your cycle goes from 1 to 45, then playblast 1 to 44.
Make sure that your extreme poses are correct, so with a walk it's the extended leg pose and your passing pose.
So frame 0 looks correct as the extended leg pose, but your passing pose is off, that's where the trouble begins. Even when checking over multiple poses, the passing one is off. x6 should have his left leg extended (so the body should be higher). Timewise it should be around x8 or 9.
Also, the walk has to be always moving. The feet have to take a step, so the move forward, once they hit the ground, they have to move backwards. But you have x0, where the front foot seems to touch the ground. But until x4 your front foot (and back one to an extend) is not moving.
Look at your feet rotation as it lifts. From x13 to around x19 the orientation stays pretty much the same. Make sure that you make it look like the foot pushes off the ground and then rotates back up.
Now, after having fixed what I mentioned above, it will all change, but what stands out right now is that your hip weight shift is not there. So look at x8, where the weight is on the screen right leg, so your hip on the right side should be up and down on the left. And don't forget to add little left and right overall body movement as the body shifts the weight over each leg.