Hi, Bob C and hello, Charley N! Just coming across this thread while searching for something else. Bob, the version Bruce Olsen referred to tells essentially the same story as the Miller/Lynn/Colony variant, but to a different tune.

Claude Simpson identified "When Arthur first in court began" from a 1603 broadside, but said the song was likely older than that, as Falstaff sings the first line of it in Henry IV pt 2, II, iv, written 1596-1599. In 1631, the text was linked in Deloney's Garland of Good Will to the tune "Flying Fame," aka "Chevy Chase," mentioned earlier. More on this in Simpson, The British Broadside Ballad and its Music, 1966, p. 98. "Chevy Chase" suits the Thomas Dibdin text that came from his play Ivanhoe, I, iii (Ann F. Howey, et al, A Bibliography of Modern Arthuriana, 1500-2000, 2006, p. 456), but it doesn't work with the Miller/Lynn/Colony texts.

Ian C's post, the Miller/Weaver/Tailor version of the song (Charles Johnson, London, 1804), is the oldest source mentioned here of a text that suits the "newer" tune -- there wasn't a link to the Bodleian broadside in the thread, so here it is if someone wants it:
http://bodley24.bodley.ox.ac.uk/cgi-bin/acwwweng/ballads/image.pl?ref=Johnson+Ballads+fol.+84&id=23017.gif&seq=1&size=1

I'd be interested in knowing if there is an earlier example of the musical notation for the second tune than the 1878 sheet music already mentioned in this thread; of the two citations given above (Leonard Deming, Boston, 1829?-1851?, and John Church, Cincinnati, 1878), only the second has notation, and that one calls the setting a "New Arrangement." Since the text had been floating around since the beginning of the century in one form or another on both sides of the Atlantic, it's plausible that there could have been other settings, even by other names, in early 19th- or even late 18th-century Anglophonic songbooks. Thanks!