Rob Naylor has the color history a bit scrambled. It's not that the ballads "are pretty clear" that the color is "greyne" rather than "grene." For one thing, anyone looking for such consistency and fine distinction in Middle English spelling is sure to be disappointed! Rather, what Rob is referring to is the fact that, in the first fytte of the Geste of Robyn Hode, Little John refers to Robin having cloth of "scarlet and grene" to supply the threadbare knight with clothes. Scholars SPECULATE that this phrase might originally have been "Scarlet in Graine," a particularly rich form of scarlet. In fact, however, the text that has come down, printed about 1450-1500, SAYS "scarlet and grene," which clearly means "scarlet and green." "Grene" is the same spelling used to describe "the grene wood," and "grene levys" throughout the text, so by the time of the first written copies it was understood that Robin has bolts of scarlet cloth AND green cloth to give to the knight. (Again, this whole passage refers to cloth that Robin has on hand to give to the knight, not to the clothes that he and his men are wearing.)

At every other place in the ballad where clothes are mentioned, it states "Lincoln grene," "grene mantel," etc, with the same spelling as "grene wood" and "grene levys," so unless Robin lives in a red forest with red leaves, it is clear throughout the Geste that whoever wrote it down thought of all the clothing as green, not red.

Another early text states "Kendall grene," again a form of green, and none of the other early texts (Monk, Friar, the Potter ballad, or the Potter play) refers to the color of Robin's clothes at all. So the idea of a red-clad Robin is based on scholarly speculation about a phrase used only once in one text. Whether this should be taken as definitive evidence that the cloth was red is, I think, doubtful.

BTW, the misconception that the ballads actually say "Lincoln Graine" was popularized a few years ago on the quiz show QI, with Stephen Fry, which was constantly looking for "gotcha" questions. It suited their purpose to ask "what color were Robin Hood's tights?" and answer "red." But a quiz show is not a good source of historical scholarship. Anyway, now all the texts are online here, so anyone who cares to can see for him- (or her-) self what the texts actually say!