A paper published today in Nature (McPherron et al, 2010) reports the discovery of 3.4 million year old bones from Dikika in the Lower Awash Valley, Ethiopia with cut marks claimed to have been made by stone tools - some 800,000 years before the oldest-known stone tools from nearby Gona. The only hominins known from the region during this time period is Australopithecus afarensis ("Lucy").
The evidence is not overwhelming - no actual tools were recovered and the marks could be due to other causes. But if hominins were butchering carcasses 3.4 million years ago and meat was a significant part of their diet a million years before the appearance of Homo habilis, it would be a problem for the "expensive tissue" hypothesis that proposes that a switch to a meat-based diet released the constraint on brain size, allowing larger-brained hominins such as Homo habilis and Homo ergaster to appear. See this entry on Prof. Hawks ever-informative blog: