Condition of the Rapa Nui when contacted by Europeans
It's fairly clear from the early European accounts that the islanders were not starving - in fact all of them speak toward the willingness of the inhabitants to trade food for manufactured goods. The ship's logs from Jacob Roggeveen's landing in 1722 state;
...in particular one who seemed to be in authority over the other
headmen, for, giving a general direction that everything they had
should be fetched and laid before us, including fruit, root crops, and
poultry, the order was promptly obeyed with reverence and bowing by
those round about, as the event proved; for in a little, while they
brought a great abundance of sugar-cane, fowls, yams, and bananas; but
we gave them to understand through signs that we desired nothing,
excepting only the fowls, which were about sixty in number, and thirty
bunches of bananas, for which we paid them ample value in striped
linen, with which they appeared to be well pleased and satisfied.1
In 1774 James Cook gives a slightly different picture, noting that while he didn't see abundant surplus, it was attributable to the extent that crops were planted and the amount of labor involved. He also comments on the apparent lack of fishing as a food source given the low abundance in the coastal waters. What is conspicuously missing is any characterization of the population as undernourished.
As every thing must be raised by dint of labour, it cannot be supposed
that the inhabitants plant much more than is sufficient for
themselves; and as they are but few in number, they cannot have much
to spare to supply the wants of visitant strangers. The produce is
sweet potatoes, yams, tara or eddy root, plantains, and sugar-canes,
all pretty good, the potatoes especially, which are the best of the
kind I ever tasted. Gourds they have also, but so very few, that a
cocoa-nut shell was the most valuable thing we could give them. They
have a few tame fowls, such as cocks and hens, small but well tasted.
They have also rats, which it seems they eat; for I saw a man with
some dead ones in his hand, and he seemed unwilling to part with them,
giving me to understand they were for food. Of land-birds there were
hardly any, and sea-birds but few; these were men-of-war, tropic, and
egg-birds, noddies, tern, &c. The coast seemed not to abound with
fish, at least we could catch none with hook and line, and it was but
very little we saw among the natives.2
The Hunt and Lipo Late Arrival Hypothesis
You can get a little better understanding of the hypothesis put forward in the article linked to in the question in this Terry Hunt's 2006 paper in American Scientist3. Much of the hypothesis put forward in The Statues That Walked stems from the conclusion that Hunt puts forward in that paper - that the settlement of Easter Island occurred much later than previously claimed (this effects population growth estimates and rate of deforestation). This claim is rejected (with the requisite amount of academic politeness) by quite a few others in the field based on what they see as flaws in Hunt's methodology. Bahn and Flenley write in their broadside rebuttal of the book that;
In fact, at the base of the Anakena excavation there is a change from
blown sand (above) to clay (below). Such an abrupt change, known to
geologists as an ‘unconformity’, indicates clearly that there is a gap
in deposition and that an unknown number of centuries are missing.
Therefore, to conclude from their excavation that the basal date in
the sand is the date of arrival of people is ridiculous.4
This is further echoed by Mieth and Bork, who make a strong case that evidence of agricultural activity on the Island points to a much earlier settlement date.
As mentioned earlier, based on radiocarbon data taken from the oldest
occupation layer found at Anakena, and by the rejection of several
older radiocarbon dates taken by other authors, Hunt and Lipo (2006)
assume that Rapa Nui was not occupied before 1200 AD.
However, our own findings concerning the development of land use
mentioned below (relics of extensive horticulture in the palm woodland
before 1200 AD, widespread and extreme labor-intensive woodland
clearance as early as 1250 AD) are strong arguments in favor of
colonization considerably before 1100 AD.5
Rats, deforestation, and food pressure
First, "the idea that the island was covered in giant palms" is not disputed by any of the research about the Island. In addition the pollen studies that Diamond cited in Collapse, Mieth and Bork undertook an extensive study of palm root casts and came up with the estimate that roughly 16 million palm trees once covered the island6. The theory of population pressure leading to deforestation is not presented in terms of how many people there were to support - it is put forward in the context of evidence of slash and burn agriculture. Mieth and Bork's article explains that the earliest instances of farming are integrated into the forest environment.
The oldest cultural layers we found are garden soils that were
integrated into the palm woodland. These garden soils are preserved
between the undisturbed casts of the palm roots and underneath later
cultural horizons (Fig. 5A(3) and Fig. 5B(3); Mieth and Bork, 2004,
pp. 52–53 and p. 65, Fig. 35A). Thus, early crop cultivation was
obviously an integrated part of the palm woodland with the advantage
that the palms protected the gardens from drying, from harsh winds,
runoff, and soil erosion by water and wind.7
This is in contrast to what is evidenced later, which is reminiscent of agricultural deforestation:
Numerous remains of burned palm stumps in the soils at several
locations on the island (Fig. 6) support the hypothesis that the
burning was caused by humans, not by natural events. Many palmwere cut
efficiently a few centimeters above the soil surface. This is evident
by clean cut, truncated surfaces of burned palm stumps which we found
in situ at many sites on the island. Other parts of the palms (e.g.
their leaves), and probably also parts of other trees and shrubs, were
left on the surface and burned in large fires. We found charred plant
remains of different macroscopic structures in the extensive burn
layers around the palm stumps. The extraction of the very strong palm
stumps was hard work for the people who cleared the land. Instead of
pulling the stumps, they seem to have piled up dry plant material on
top of them to increase their flammability. On some stumps we found
carbonized stalks of grass which were used as fuel (Mieth and Bork,
2003, p. 74; KIA 19369,Table 1).8
Diamond pointedly notes in his critique of The Statues That Walked that Hunt and Lipo have remained completely silent about this line of research9, which is puzzling in that it was well known before they published. As to the rat theory, he dismisses it similarly to Mieth and Bork.
Rats occur not only on Easter but also on every other one of the
hundreds of other Polynesian islands, most of which nevertheless did
not end up deforested. Over 90% of preserved palm seeds outside caves
were not gnawed by rats. Easter’s forest consisted not only of the
palm but also of at least two dozen other species of trees and other
plants, all of which also became extinct on Easter although most of
them are not known to suffer seed predation by rats and continue to
exist in the presence of rats on other Polynesian islands. The Hawaii
study does not demonstrate, but merely speculates about, a role of
rats in deforestation on Hawaii.10
Note regarding population
Not directly related to the question, but interesting none the less (given the doubt raised about population estimates in the other answer) - J. C. Sprott wrote a great paper from a more mathematical standpoint and used statistical modelling to estimate a peak population of around 10,000. The more fascinating piece of the paper is his model of a three bio-type system of humans, rats, and palms that creates a strange attractor in multiple formulations of species interaction. It makes a strong case that the overall system was very susceptible to sudden ecological collapse.11
Conclusions (tl;dr)
Given compelling evidence of agriculturally related deforestation and a poorly substantiated case for rats as the primary factor, I personally think that Hunt and Lipo's theory is dubious at best. The shift between low intensity farming and high intensity farming (which seems to disappear by the time the Europeans show up in the 18 century) points strongly to a population collapse. Whether the collapse itself was due specifically to food pressures or other causes is up in the air.
1 Corney, Bolton Glanvill, editor. The Voyage of Captain Don Felipe González, p.13
2 Cook, James. A Voyage Towards the South Pole and Round the World, Volume 1, eBook
3 Hunt, Terry. "Rethinking the Fall of Easter Island", American Scientist Sept.-Oct. 2006, Online
4 Bahn, Paul and Flenley, John. "Rats, men or dead ducks", Current World Archaeology, Issue 49, p. 8
5 Mieth, Andreas and Bork, Hans-Rudolf. "Humans, climate or introduced rats" in Journal of Archaeological Science (2009) 1-10, p. 2
6 Ibid, p. 1
7 Ibid, p. 6
8 Ibid, p. 6-7
9 Lynas, Mark (Sep. 22, 2011). Re: The myths of Easter Island – Jared Diamond responds (Blog).
10 Ibid
11 Sprott, J. C. "Chaos in Easter Island Ecology", Nonlinear Dynamics, Psychology, and Life Sciences, Vol. 15, No. 4.