Okay, this is may be wrong, but I'm gonna write this anyway:
I found a word in the bionicle lexicon on Bionicle.com. The word is "Brakas", they say that Brakas is the name of an ape-like creature. (GregF, are you there?)
The weird thing is, that TLC has never provided any information about that ape. No pictures, no legends, no nothing. Without the word in the lexicon, we even wouldn't know it's there.
Let's move on to my theory:
I think that the brakas was an extinct species of ape that lived on Mata-Nui, and, in some point of time, the brakas evolved into the early matoran, which look like the 2003 or maybe even the 2004 matoran.
An ice age, a natural disaster or animals with higher position in the food chain, forced those "Cave-Matoran" to hide beneath the surface, which means, in Matru-Nui. There, Mata-Nui came and gave them culture, turning the scavenging, perhaps even cannibalistic, ape-like cave-matoran into more civilized lifeforms. Then, Makuta came and turned them to McToran, and the toa arrive, and all the bla-bla-bla begins.
What do you think? Post commens please!