According to the Candy Land 50th Anniversary Edition Rules:
1985: “The Legend of the Lost Candy Castle” story and characters introduced to game.
I presume, Since Lord Licorice is the antagonist of that story, that he was introduced then.
'They'll never find the hidden King or his Castle,' Lord Licorice says sourly... 'for I have hidden them from sight so that all of Candy Land will be mine!' His heart is as hard as rock candy. Always gloomy, always grim, Lord Licorice lives very much alone, except for the few Bitter Chocolate Bats to keep him company!
'Utter nonsense,' Queen Frostine says of Lord Licorice's evil plan. Peacefully adrift on an Ice Cream Float in an Ice Cream Sea, warm-hearted Frostine thinks the Candy Land Kids will surely find the King. 'And no matter how many times Lord Licorice plots and plans,' she adds, 'Candy Land will sparkle once again.'
EDIT:
I found the History Page on Hasbro's site. It appears that the version labeled "1980s" has Lord Licorice, while the "1970s" version does not. According to the Candy Land wikipedia page, there was a version published in 1978, and another in 1985. I've done some web searches, and "1984 edition" comes up in searches. Perhaps there were different copyright/publishing dates in different countries?
Anyway, I can't find any reference to Lord Licorice on boards for the 1978 or earlier editions…