I you want to see a ton of different walking robot designs, check out
this page. (You'll have to scroll down a bit.) I know that these are Lego creations, but the principles behind the walking robots can be adapted to a larger scale. IMHO, I would think that instead of rotating the entire leg around, do as Kevin Sevcik suggested, and make the legs go up and down, instead of in circles. Similar to this picture:
I know that it wouldn't be able to go up stairs, but it would have much less stress on the shafts.
Also, I am curious. What is the size of your leg?
