The up and down motion you added definitely helps a lot. He now has more weight and mass.
The forward motion is still a little jerky though (in both clamped and spline versions). It looks like he's either lunging forward on each step or straining to make large strides. I think the problem here is the expression on the root. The torso stops moving everytime the feet are planted, which doesn't feel natural at all. One option is to reduce the contact time for each step. Another option is to remove the expression from the root and hand key the root's transforms to give it smoother motion.
I don't know if this will help or not, but here is a (slightly exaggerated) breakdown of a walk cycle that I did for my students last term:
This is based directly off of the walk sequences in Richard Williams' book The Animator's Survival Kit. Even though this was a Flash animation, it still applied to 3D. The thing you'll notice about the walk is the continuous motion of the torso. You can draw a clean sine wave that traces the torso's motion across the frame. Your character's root translate should be the same. Also, the position of the torso is shifted forward slightly, so that more weight is on the leading foot. In your rigging image, it looks like the root is centered exactly between the feet, which isn't entirely correct.
Anyhow, I hope this helps. I look foward to seeing more progress on this scene.