The key phrase there in Koheles is "under the sun." The Gemara (Shabbos 30b) explains that this means the natural world, as opposed to Torah which was created "before the sun." (Rashi to Eccles. 1:3 explains a little differently: תחת can also mean "instead," and "sun" symbolizes the light of Torah, so תחת השמש means "things done instead of Torah study.")
The era of Moshiach, then, doesn't have to be subject to the same constraints of "nothing new." If, as the Midrash (Vayikra Rabbah 13:3, paraphrasing Is. 51:4) states, at that time there will be "a new Torah" (i.e., new dimensions of Torah that were never revealed before), then by the same token there can be novelties in the natural order. (Consider Isaiah's prophecy about "the wolf living peacefully with the lamb," which according to many opinions - albeit not Rambam - means just that. For that matter, consider the resurrection of the dead, for which so far the only precedents have been Eliyahu's and Elisha's actions, and which certainly is not part of the natural order we know.)
R. Menachem Mendel Schneersohn (the "Tzemach Tzedek"), if I'm understanding him correctly, makes basically the same point in his Beurei HaZohar (in Kabbalistic terms). The order of things that we're used to is that malchus1 depends on what it receives from z"a,2 paralleling how the earth depends on the sun to produce vegetation; in Moshiach's times the earth (and its analogue malchus) will be "beyond the sun" of z"a and will not need to receive Divine beneficence through it. (In other places in Chassidus, too, it is explained that this is in fact not something new, but a revelation of something that was true all along: that the spiritual source of malchus/female is higher than that of z"a/male.)
"Kingship," the lowest of the ten sefiros, which also represents femininity.
Acronym for ze'er anpin ("small face"), the six sefiros from chessed ("kindness") through yesod ("foundation"), which also represent masculinity.
