"Et Shabtotai tishmoru u'mikdashi tira'u Ani Hashem" -- "You shall keep my Sabbaths and fear my Temple; I am G-d" (Kedoshim 19:30). Rashi, commenting on this passuk, quotes the Talmud (Y'vamot 6a) that the Beit HaMikdash may not be constructed on Shabbos (see Rashi at the beginning of Parshas VaYakhel where he records a similar d'rasha concerning the Mishkan). The same halacha applies to Yom Tov (see Sh'vuot 15b). Thematically, the prepatory activities to cause the Shechina to dwell among the B'nai Yisrael do not push aside the Shabbos, the testimony to the creation of the world. However, the 'Avoda (sacrificial order) in the Beit HaMikdash must be performed on Shabbos even if it involves violation of the laws of Shabbos. R. Meir Simcha HaKohein of Dvinsk, in his commentary, Meshech Chochma, (Parshas VaYakhel) explains that whereas Shabbos serves as a testament to G-d as Creator, Mikdash, as the place of hashra'at haShechina, and the 'Avoda offered in its walls serve as a visual sign of G-d as the Mashgiach al Hakol, the One who is constantly aware of and intervenes in the history of B'nei Yisrael and mankind in general. Since the second theme goes beyond the first, the 'Avoda is therefore doche (pushes aside) Shabbos. A major theological plank of Judaism, as evidenced by Y'tziat Mitzryaim -- the Exodus from Egypt -- and the subsequent Revelation at Har Sinai, is that G-d is constantly involved in the world which He created. This is in sharp contradistinction to the philosophy of Deism, held by many ancient as well as recent philosophers, that G-d created the world and then left it totally to mankind. The first principle of faith delineated by Rambam in his introduction to Perek Cheilek in Tractate Sanhedrin, is that Hashem is not only the Borai Olam (Creator) but also the Manhig (Overseer).
This halacha that binyan haMikdash (Temple construction) is not doche Shabbos or Yom Tov seems to be contradicted by a G'mara in Rosh Hashana (30a). There, the Talmud records R. Yochanan ben Zakkai's enactment concerning the prohibition of chadash. By Torah law, grain products whose stalks took root in the ground after the second day of Pesach, may only be eaten after the Korban 'Omer was offered on the subsequent year's second day of Pesach. After the destruction of the second Temple, since the 'Omer was no longer brought, R. Yochanan b. Zakkai instituted that the grain from the new crop may not be consumed during the entire second day of Pesach. Now, by Torah law, when there is no Temple, the grain may be consumed as of dawn of the second day (see discussion there that not all agree to this point). However, if, in the post-Temple era, people would become accustomed to eat the new grain from dawn, this might lead to a violation of the laws of chadash. M'haira yibane haMikdash -- the Temple may speedily be rebuilt -- at which time the Korban 'Omer will once again be brought, and people would erroneously think that they need not wait for its being offered on the Altar before eating chadash. The G'mara questions this reasoning: if it is built before the second day of Pesach, the 'Omer would certainly be brought by noon (the kohanim would certainly not be lax about it), in which case there would only be a need to institute a prohibition in the post-Temple period against eating chadash until noon. To this, the G'mara concludes that it might be built late on the first day of Passover, and, due to the flurry of activity necessary on "opening day," the 'Omer might not be brought until very late on the second day. On this, Rashi questions how the Beit haMikdash could be rebuilt on Yom Tov. After all, as we discussed above, binyan Beit haMikdash is not doche Shabbos or Yom Tov. Rashi answers by quoting the famous Midrash that the Third Temple will not be rebuilt by Man. Rather, it has already been built in Heaven by G-d and will descend miraculously at the appointed time. This miracle is not subject to the aforementioned rule!
However, this answer will not resolve this difficulty according to Rambam. For Rambam in his Hilchot Beit haBechira (1:12) records the law that the construction of the Temple does not override Yom Tov. The Rambam is obviously recording these laws with reference to the building of the Third Temple. Furthermore, in Hilchot M'lachim (11:4), the Rambam writes that the Third Beit haMikdash will be rebuilt by the Melech HaMashiach, the Messiah. The Rambam even indicates that this is one of the proofs to positively identify the Mashiach -- the one who gathers all the dispersed of Israel, wages war against the enemies of Israel, and rebuilds the Third Temple. The Rambam then maintains that the Third Beit haMikdash will be built by Man and is therefore subject to the restriction against building on Yom Tov. The above G'mara therefore remains difficult.
Perhaps we can suggest an answer based on an approach discussed by R. Menachem Mendel Schneerson, ZT"L, the late Lubavitcher Rebbe. In Tractate Sanhedrin (98a) we learn that the G'eula (Redemption) and Biat HaMashiach (Coming of the Messiah) can take place in one of two ways depending on the deeds of K'lal Yisrael. If lo zachu, we do not truly merit the redemption, then the G'eula and Biat HaMashiach will occur at their predetermined time and will unfold in a natural way. If Klal Yisrael merits, then the redemption will be hastened and will occur supernaturally. Similary, R. Schneerson suggests, if we do not merit, then the Beit haMikdash will be rebuilt by Man as the Rambam indicates. If we do merit, then the Temple will descend from Heaven as Rashi indicates. We can develop this answer further to explain how the Rambam would resolve the difficult G'mara in Rosh Hashana. R. Yochanan b. Zakkai lived at the time of the destruction of the second Temple. The G'mara in Sanhedrin (97a) indicates that the time in history that has been predesignated for Biat Hamashiach is during the last two thousand years of the existence of the current world as we know it, from the years 4000 - 6000 in the Jewish calendar. R. Yochanan b. Zakkai lived before the year 4000. Therefore, his concern that "m'haira yibaneh haMikdash" -- that the Temple would be built speedily -- would clearly have to be based on the merits of Klal Yisrael. This would lead to the supernatural G'eula which would include the Mikdash descending from Heaven. As such there was a real concern that the Mikdash would be built on the first day of Pesach and therefore chadash had to be prohibited for the entire second day.
The various institutions that have been established by our Chachamim based on the principle of "m'haira yibaneh haMikdash" (see Encylopedia Talmudit, "Beit haMikdash": "m'haira yibaneh haMikdash"), should serve to highlight to us the constant yearning that Klal Yisrael have had and must have for Geula, Mashiach and binyan Bayit. These themes fill our prayers especially on Shabbos and Yom Tov. The Talmud in Shabbat teaches that one of the first questions that the soul is asked in heaven is "tzipita li'shua?" -- "did you anxiously await redemption?" Part of the fundamental principle of belief in the coming of Mashiach as elaborated upon by the Rambam (Hilchot M'lachim 11:1) is not just belief in but a longing for redemption. Due to the many blessings that Hashem has bestowed on his people in all the lands of their dispersion, especially in our time, this longing is not innate and must be constantly developed. Some recommend that minimally when we pray "Ki lishuat'cha kivinu kol hayom" -- "for we long for your salvation every day" -- in the15th blessing of Shemoneh 'Esrai, we should strive to feel immense longing for the redemption. In the merit of our longing for the G'eula, may we merit it speedily in our days!