Walking Issues

Take a look at this video from Dave Werner on the Character Animator team: https://www.youtube.com/watch?v=gv_2Upvtm-M

You can also look at one of the other example puppets that's setup for walking. I think the problem might be with your hips are (or aren't) rigged. I've come across this issue myself. Put the hips on the torso and make sure the green anchor of each leg aligns with the hip pins.