Here is the first attempt I've taken at a walk cycle in a long, long time.  I see plenty of issues with it, but most of them come from my sloppy inbetweening.  Overall though I think it is a good step (no pun intending) and I can't wait to get into more personality based walks.

 One thing I want to study after doing this is what happens to the knee when a leg starts bearing the weight on it.  You can see in my animation that I have the body continue down a bit as the leg absorbs the weight, which causes the knee to move forward.  Then the knee changes direction as he pushes off with that same leg.  It gives it a strange feeling that doesn't feel right.  If you know the answer, please let me know in the comments.