We tested the Legends with a group plot and it worked fine for us. If you are passing in a group plot object, you do have to use the AddLegendItem method that specifies a group number, though, numbers 0, 1, 2, and 3 below.
legend.addLegendItem("Prozac", ChartConstants.HBAR, thePlot2, 0, legendFont);
legend.addLegendItem("Zoloft", ChartConstants.HBAR, thePlot2, 1, legendFont);
legend.addLegendItem("Paxil", ChartConstants.HBAR, thePlot2, 2, legendFont);
legend.addLegendItem("Celexa", ChartConstants.HBAR, thePlot2, 3, legendFont);
Or you can just use the addLegendItem overloads where you explicitly set the color attribute, rather than use a lookup of the plot objects color attribute. They all seem to work.
If you can't figure it out show the code you used creating the legend with the MultiLinePlot.