OK.
We THINK that the Australian Aboriginals did not change the foods that they ate (by genetic selection), whereas other cultures have. We also THINK that Australian Aboriginals have been eating similar diets for around 60,000 years (well into paleolithic times), which no other culture can claim. Thus, their diets are probably more relevant to discussions about the primitive diet than any other - particularly since the diets mentioned (Inuit and Maasai) are quite a bit younger and the Maasai is arguably not primal while the Inuit is a response to extreme climate rather than the diet of 95% of primitive societies - and the Inuit do not appear to be paleolithic either.
With the Australian Aboriginals we thus have a unique view of what the paleolithic diet might look like - particularly as it is a whole continent and there are a lot of people who can actually tell us what it was (rather than having the odd preserved stomach that we can investigate from other continents).
Every river and stream in Australia and all the coastline had fish traps when the colonists came to Australia. Most of these were removed but there still exist remnants that are dated well into paleolithic times. They ate many grains (including wild rice). Meat was relatively rare in their diet, and it was lean.
Can you cite some sources that they ate many grains and that meat was relatively rare? That's not what I'm finding.
http://www.ncbi.nlm.nih.gov/pubmed/1685581 (Traditional diet and food preferences of Australian aboriginal hunter-gatherers. O'Dea K. Philos Trans R Soc Lond B Biol Sci. 1991 Nov 29;334(1270):233-40; discussion 240-1.)From the abstract:
"Available data suggest that they were physically fit and lean, and consumed a varied diet in which animal foods were a major component. Despite this, the diet was not high in fat, as wild animal carcasses have very low fat contents through most of the year, and the meat is extremely lean. Everything on an animal carcass was eaten, including the small fat depots and organ meats (which were highly prized), bone marrow, some stomach contents, peritoneal fluid and blood. A wide variety of uncultivated plant foods was eaten in the traditional diet: roots, starchy tubers, seeds, fruits and nuts."
From the full text, pg. 236: "Dietary carbohydrate in the hunter-gatherer diet was derived from uncultivated plants, (tuberous roots, fruits, berries, seeds, nuts, beans) and honey. Cereal grains, the dietary staples of man since the development of agriculture, were not a major component of the traditional Aboriginal diet."
http://www.ncbi.nlm.nih.gov/pubmed/19087457 (Australian aboriginal plant foods: a consideration of their nutritional composition and health implications. Brand-Miller JC, Holt SH. Nutr Res Rev. 1998 Jun;11(1):5-23.) From the abstract: "For at least 40-50,000 years, plants played an important but supplementary role in the animal-dominated diet of Australian Aboriginal (AA) hunter-gatherers. New knowledge of the nutrient composition and the special physiological effects of their foods provides another perspective in the current debate on the composition of the 'prudent' diet and the diet on which humans evolved. In the present paper we have calculated the average nutrient composition of over 800 Aboriginal plant foods (in total and by food group) and highlighted the differences between these and modern cultivated foods."
From the full text: "The Australian bush contains thousands of edible wild plants, ranging from sweet and tangy fruits and starchy seeds to leaves, tubers, fungi and seaweeds."
"For many years it was believed that the AA diet was predominantly vegetarian, particularly in the desert areas, but this view is no longer accepted. There is now strong evidence to show that AA diets in many areas were meat-oriented and there was a preference for meat, fat, honey and freshly harvested food (Lee, 1996). Plant foods were a supplement rather than an alternative to animal foods."
"Small cereals grains (seeds of the family Graminae) which have been staples for ‘civilized’ peoples since the Agricultural Revolution, made a surprisingly minor contribution to the diets of most hunter-gatherers (Eaton & Konner, 1985). But archaeological evidence dating back to 15 000 years ago indicates that some cereal grains (e.g. Panicum spp.) were important foods in grassland areas of Australia where river flooding was a regular occurrence."
http://informahealthcare.com/doi/full/10.3109/08830185.2012.667180 (The interplay between diet and emerging allergy: what can we learn from Indigenous Australians? Walton SF, Weir C. Int Rev Immunol. 2012 Jun;31(3):184-201.)From full-text: "Many Indigenous populations, including Indigenous Australians, ate red meat as a major component of their diet, yet this did not lead to increased levels of fat due to the lean nature of wild animal carcasses [22, 23]. Seafood was also a major part of many diets (especially in coastal communities), and carried many health benefits due to omega 3 and 6 fatty acids and lean protein content [22–24]. The beneficial nutritional components of these lean meats and fish include long-chain polyunsaturated fatty acids (PUFAs), protein, iron, zinc, vitamin C, and B complex vitamins [22, 25, 26]. In addition many traditional diets included high-level consumption of a large variety of mostly raw plant foods rich in fiber and complex carbohydrates, such as fruits, vegetables, seeds, nuts, and roots [22].