New Scientist is carrying this article summarizing new discoveries about early hominid locomotion. Two new fossil finds, Sahelanthropus tchadensis and Orrorin tugenensis, date from the critical 6-10 mya period when hominids and chimpanzees went their separate ways. By electronically scanning the Orrorin specimen, scientists have found strong evidence that hominids started walking upright very shortly after the split.
I'm beginning to wonder if perhaps walking upright was the reason for the split. Either way, bipedal locomotion has now been pushed so far back that the old "walking upright to use tools" hypothesis is now quite dead. In truth, we don't have a good reason why some of our ancestors ended up walking on two feet while others didn't.
Update: this MSNBC article also includes a nifty computer scan picture of the fossil bit in question.