There is a major dispute in the medieval Rabbinic authorities about how to understand that Gemora. (see the Biur Halacha on Orach Chaim 530.) Some understand that the work on Chol Hamoed is rabbinically prohibited, with this Gemora being an asmachta. According to that, they probably did work until the prohibition against it was enacted. Unless Moshe Rabbeinu himself first added this rabbinical prohibition.
Others understand it to be saying that work on Chol Hamoed is Biblically prohibited. According to that, there must have been some work prohibitions on Chol Hamoed.
The concept of "Lo mosron Hakosov eleh l'chachomim" (that the Torah left it up to Chazal to figure out the exact parameter) comes up elsewhere too. The Chazon Ish (Yodoyim 8:17) explains the concept in a general sense: There frequently are competing calculations of the correct course of action. In halachic terms: "mi nidcha mpnei mi". The Torah is instructing the Rabbis to decide on the proper one. (I.e. which work prohibition would or would not have other considerations causing them (not) to be prohibited.)
Possibility: Long ago, which work was prohibited on Chol Hamoed was decided by the Rabbis of that generation, depending on the situations they were facing. Afterwards there came a time when a universal Rabbinic consensus made the rules permanent and immutable.
The later authorities cite an oft-quoted Gemora in Yerushalmi. In this Gemora, Rav Abba Bar Mommal said: If he could find others who agree with him, he would allow some of the prohibited work on Chol Hamoed. The later authorities cite this Gemora as an indication that there was a possible fluid nature of the work prohibition on Chol Ha'Moed at that time. Even if a Beis Din (Jewish court) that was bigger in number and wisdom had already prohibited that particular work prohibition. However, the authorities don't consider this proof to be 100% conclusive.
