My guess of what happened was that the potatoes were sitting in an open pot that was not in a rolling boil. I'm going to assume that they went down from the pass and the place where "they took up [their] quarters" was at 11,000ft. This region was then, as it is today, almost destitute of vegetation. Darwin notes in the paragraph just before the potato comment that
The root of a small scrubby plant served as fuel, but it made a miserable fire, and the wind was piercingly cold.
Temperatures in that region average close in the 2 to 4C in March. The poor fuel and the winds make it likely that there was no rolling boil and that while parts of the pot may have been at 89C (the boiling temperature at 11000ft) it is likely that the rest of the pot was not. The poor fuel and the cold and dry wind all contributed to the lower temperatures, not just the air pressure. Bubbles form at the bottom of the pot and rise, so the water appears to be boiling, but it is far from the boiling temperature near the upper walls.
I have experienced this problem using my modern MSR backpacking stove, so I imagine it must have been harder with a camp fire. I got the impression they were not carrying tents. Darwin notes that the next day (after the night of the uncooked potatoes) they found shelter under "some large fragments of rock." This makes it likely that there was no cooking inside some big tent and given the meagerness of their equipment, that the pots had no lids.
Darwin left Chile towards Mendoza on 18 March 1835 not along what are today Route 60 in Chile and Route 7 in Argentina, but up the Yeso Valley. When you cross the border you go through the Piuquenes Pass, which is at 13,235ft. What could be reached within a day's walk in the valley below is 10500ft or higher. So the assumption of 11000ft for where the potatoes where boiled seems reasonable.
Blanching at low temperatures (between 55C and 75C) for a little less than half an hour is a known technique for adding firmness to fruits and vegetables that will later be cooked in some other form (see page 283 of McGhee). Figure 2 in the study of potato blanching by Abu-Ghannam and Crowley, shows that potatoes cooked for an hour at 75C or lower had the same firmness of raw potatoes. As the blanching temperature increases to 90C, the softness of a cooked potato is reached in 30 minutes, with 80C being the approximate transition temperature for going into the cooked state.
The results of Abu-Ghannam and Crowley are in line with some of the sous-vide results I have seen, but not all. My guess is that depending on the balance between starch and cellulose the temperature at which pectin stops holding things together can vary.
Water boils at lower temperatures at higher elevations, but drops only to 80C at 19,000ft:
3353m 11,000ft 89C
4572m 15,000ft 85C
5791m 19,000ft 80C