Hey man... I'm another newbie. I have that exact same book...and I have to say I'm totally with you on the primitive man...the book explains how...but not really WHY you're doing everything you do ((And they don't even do a very good job of explaining how....just step by step. )) 8-)
Best way to start with walk cycles is not to bind the skeleton to the model....create some inorganic mechanical-looking model and PARENT (important..do NOT bind) each individual geometry (or group) to whatever joint will effect it. It'll be much easier to work with, as Maya will only have to calculate translations and not deformation. You should end up with something remotely like:
My workflow is:
Model - but if you're using premade, I'm assuming it's already built, grouped properly and positioned for animation.
Skeleton - always work from the pelvis (or whatever will be acting as the pelvis) out. Parenting a joint to another joint connects the two with a bone...just fyi.
Binding/Parenting - If you're building something metallic...it won't need to deform. So instead of binding...you do the much much easier task of parenting the geometry to the joints. More tedious..but MUCH easier for a beginner to deal with because he/she won't need to use lattices and deformers to learn to animate.
The easiest way to do this is just use the outliner to manually select and parent each surface/polygon object to the joint that will MOST effect it. i.e....the thigh will be parented to the hip joint, the foot will be parented to the ankle joint. This will allow you to translate those parts easily during animation and create convincing motion.
IK- With a leg..click from the ankle to the hip...the ball to the ankle and the toe to the ball with IK joints. That'll give you much more tangible control than the Foundation's goofy reverse foot. Also..with a mechanical object, you won't have to worry about rolling the foot...so there's a deformation gone. Create locators that'll control the IK handles and parent them. Hide the IK handles. Always test the motion...if it doesn't behave right---try rearranging the handles/end effectors.
Bear in mind, you will need to enter an expression into your expression editor to get the pelvis to move with the legs. If you have the book...you can reference how to do that.
Animate- Be sure to have your geometry either on or near the origin. You don't have to...but it does make life easier. I use a 60 frame clip..as the 30 frame is a bit too fast for my taste...and this is a mechanical construct..so viewers wouldn't expect it to move as quickly as something that was alive. Set keys to get a sliding motion of the feet...try to be as exact as possible...if you aren't you can always go into the Graph Editor and edit the curves to make it exact (which you'll have to do anyway...to make sure it takes even strides with both/all of it's feet). After you've got a correct sliding motion (you'll know it when you see it, especially if you...unlike me, had the patience to complete primitive man), just set the keys for the rise of the feet and enter an expression into the editor for the rise of the pelvis..something like:
body.ty = (leftleg.ty + rightleg.ty)/2;
After that it's all about refining the motion via the graph editor to get something that looks convincing.
Here's a link to a REALLY good tutorial on how to do this..it's great for learning a walk cycle without having to do a whole lot else...naturally as you feel more confident, you'll want to add more and more.
Maya Tutorials - Star Wars Walker