I agree with what's been said, and your arm motion looks really really good.
The main problem seems to be there's no bend with the legs of the weight of the character. Almost like the character's being held up by a rope by the waist. The head bob should also be a bit smother, and maybe work some horizontal movement in there as well.
The spine also is jiggly and should bend and move with the character a bit more. Specifically it should be rotated to the right a bit more (you lean into a run, so the spine shouldn't be as straight as it is here.)
Also your sprite goes into the contact frame too quickly, and you have a passing frame that lasts one frame too long (I think.)
Check idle worm's walk cycle
here. Once you know the basics of walk cycles, a run cycle becomes easy and fun.
EDIT: Heheh, you posted a new walk cycle right when I was about to post this!
The new one is better, the legs are definitely smoother. Now I'd add a bit of a lean and some back and forth head motion (only a few pixel lengths back and forth. Like, 1 or 2, and see how that works.)