This reminds me of an article I saw in 5280 (local Denver mag), or some such, about an indigenous people in Mexico. Running is a big part of their culture and they run long distances and difficult terrain in sandals.
Wikipedia Link: http://en.wikipedia.org/wiki/Tarahumara
[edit]: Here is the 5280 article, which goes into some interesting details: http://www.5280.com/issues/2009/0905/feature.php?pageID=1691