Shocker of shockers, the favorite dietary exemplars of the Zero Carbers, the Eskimos and Vilhjalmur Stefansson, ate potatoes. The wild potato that was most commonly eaten by the Eskimos was even named after them--"Eskimo potato" (aka Indian potato; the plant is called masuqutaq in the Iñupiatun/Inupiat dialects; http://en.wikipedia.org/wiki/Eskimo_potato, http://www.sil.org/silepubs/Pubs/928474543482/Seiler_Inupiatun_Eskimo_Dictionary_LCDD_16.pdf). Did the Eskimos regard Eskimo potato as a food fit to eat only to avoid starvation, or as a "fallback food"? Not according to Bear Grylls. I watched a Bear Grylls video last night, and by coincidence, he found, ate (raw) and expounded upon Eskimo potato...

26:14 "If you know what to look for, there are all sorts of berries and plants you can eat with your fish [in Alaska]. This is ESKIMO POTATO, this plant, here. I pull this up and get to the root of it. This is all edible [displaying the root]. At this time of year it's all a bit stringy, and the best way really is to roast this on a fire, but you can eat this ... raw. It's a bit muddy (laugh), but a really, really good food source, and many people say it's the most valuable food source in all of Alaska. These roots are full of starch and carbohydrate. It's hardly a gourmet meal, but it will keep me moving a little longer." --Bear Grylls, Man vs. Wild, Season 1, Episode 3, "Alaskan Mountain Range"

Here's one part of Stefansson's The Fat of the Land that tends to get skipped over by Zero Carbers--limited potatoes were allowed in Stefansson's idea of an "Eskimo diet" (I capitalized mentions of potatoes/tubers in the following excerpts to make them easier to find):
  "While there were in pre-white times many Eskimos who used no vegetables, there were some, especially in Labrador and Alaska, who got as many calories from vegetables as the Holiday Diet (aka the Dupont diet, aka the Dupont-Holiday diet, developed by Dr. Alfred W. Pennington) does; so, even with a few things like lettuce and POTATO, we may well name this regimen for the Eskimos. The same diet is described in my 1921 book Friendly Arctic, as used and enjoyed by whites who, like the Eskimos, found it nonfattening, and thus a good reducing menu." (The Fat of the Land, 1960, p. xxvi)

Pennington's Dupont diet, reported as "The-Eat-All-You-Want Reducing Diet" in Holiday Magazine in 1959:
20+% calories from lean meat
50+% calories from fat
under 30% calories from carbohydrates and fiber, such as "a small helping of BAKED POTATO, fresh fruit, or salad-type vegetables."
  
Despite the nearly 30% carbs allowed (not even considered low carb by many LC diehards today), Stefansson strangely referred to this as a "nearly all-meat diet." (Source: FOTL, p. xxiv)
  
Here is the Basic Seven Diet that Stefansson mentioned in Fat of the Land and apparently tended to eat when he wasn't eating his Sage-Bellevue mostly-meat diet. The Basic Seven Diet contains even more carbs than the Dupont-Holiday diet he reviewed favorably in FOTL that included potatoes:

"THE BASIC SEVEN DIET

Eat Some Food From Each Group Every Day

Group 1: Green and yellow vegetables: some raw, some cooked, frozen or canned.
Group 2: Oranges, tomatoes, grapefruit, or raw cabbage or salad greens.
Group 3: POTATOES and other vegetables and fruits: Raw, dried, cooked, frozen or canned.
Group 4: Milk and milk products fluid, evaporated, dried milk, or cheese.
Group 5: Meat, poultry, fish or eggs or dried beans, peas, nuts, or peanut butter.
Group 6: Bread, flour and cereals, natural or whole grain or enriched or restored.
Group 7: Butter and fortified margarine (with added Vitamin A).
IN ADDITION TO THE BASIC 7 . . . EAT ANY OTHER FOODS YOU WANT."

The claim was that you could eating anything you wanted and stay healthy as long as you ate something from each of these food groups (sources: http://forum.zeroinginonhealth.com/showthread.php?tid=27 and Fat of the Land). It's also interesting that two of the food groups contain fruits. Of course, Stefansson reported that he fared better on his Sage-Bellevue diet than on the Basic 7 diet, so he wasn't claiming that the Basic 7 was optimal, but he apparently felt it was good enough for him to live on.

Another interesting factoid is that the maned wolf eats (raw) wild tubers:

"Diet
The maned wolf specializes in small and medium-sized prey, including small mammals (typically rodents and hares), birds, and even fish.[14][11] A large fraction of its diet (over 50%, according to some studies) is vegetable matter, including sugarcane, TUBERS, and fruit (especially the wolf apple (Solanum lycocarpum).[15] Captive maned wolves were traditionally fed meat-heavy diets and developed bladder stones. Zoo diets now feature fruits and vegetables, as well as meat and dog chow." (http://en.wikipedia.org/wiki/Maned_wolf)

So traditional Eskimos, Stefansson and maned wolves all ate/eat tubers, with the Eskimos and Stefansson apparently regarding them as at least relatively healthy. Perhaps we shouldn't rule all tubers out as "not Paleo" without more evidence?