I would say that the rules mean you must be able to make the legs move up bad down without moving forwards and backwards and then must do the opposite making them move forward and backwards. However I don't think you have to make each leg act independently- you can have motor to make all the legs move up and down at different times and then another motor for each side to control forward and backwards- you then just need some complicated electronic jiggerypokary to make the legs co-ordinate to move in the correct manner.
I personally feel that both of Craig's robots should be allowed (although I believe he has no desire fight with them?) and they clearly are walking and look very cool but I understand by allowing mechanisms like that it could be easy to take advantage of the rule and make something that is barely a walker to qualify for the weight advantage.