On the wild assumption the "early" does have such a specific meaning, a Google search using "gnostic withy" comes up with a book review as the second entry, which claims The Bitter Withy is based on Gnostic tradition. Obviously, no-one is claiming the song is anything like that old, but its not impossible that the story could be. (I spend a few minutes looking through a pile of gnostic writings but got bored before I found anything like the story. Others are welcome to try.)

If anyone does have the patience to plough through all that stuff, and they come across the tale for "On Christmas Day", please post a full reference!