Ha! Yes, I thought recognised that tutorial from the way your animation behaved. I'm usually a big fan of Slynyrd but this sequence, in particular, seems to create animations with a kind of unnatural flicking motion and oddly tentative feet that don't really leave the ground much. Maybe it's just me, but I just don't get on with the way the legs move.
I would suggest remaking it based on a different cycle. I've had success using the Animator's Survival Kit. The relevant page is reproduced here:
http://www.angryanimator.com/word/2018/03/20/preston-blair-deciphered/or find another one you like. Searching Google Images for "run cycle animation" or "walk cycle animation" should yield many examples.
Make sure that when feet are in contact with the ground, they always move the same number of pixels back per frame.
But basically I think basing your animation on a different cycle should fix your issues.