The first to address this custom in a meaningful manner was R. Azariah m'Fano, one the leading kabbalists of his day.
This is what one should do if they want to properly remove their teffilin on Rosh Hodesh. One should remove the teffilin right after shemoneh esreh and one should not wait until after u'va l'tzyion like other days . . . it is proper to remove them before one reads from the torah the portion discussing the mussaf sacrifice . . . and if one removes them before hallel this is even better . . . u'va l'tzyion on the day of Rosh Hodesh is really part of the mussaf . . . and it is wholly improper to wait to remove the teffilin right before one is going to start mussaf as this is worse than Yeravam who removed his teffilin before the king (Sanhederin 101b), there he only removed them in front of an earthly king but one who waits to remove his teffilin until right before mussaf is doing so in front of God.Thus, R. Fano has two basic points. First, one should not wear teffilin for any portion of the prayers connected with Rosh Hodesh and therefore one should preferably remove them before hallel but at the very least before reading the Torah. Second, one should certianly not remove them right before starting mussaf as this is highly disrespectful to God.
R. Mordechi Yaffo, in his Levush also says that one should remove them before the reading of the torah. R. Eliyahu Shapiro in his Eliyahu Rabba and Zuta quotes R. Fano and agrees that one should not remove them right before mussaf. R. Karo in Shulchan Orakh just states that one shouldn't wear them for mussaf but does not say when one should remove them. R. Moshe Isserles does the same. In fact, on Hol HaMo'ad, those who wear teffilin remove them not right before mussaf but instead before hallel.
So one may be asking themselves, well if everyone that disucsses when one should take them off says to do so much earlier than we do, how come no one does that now. And for that, we need to turn to R. Avroahom (hamechune Abeli) Gombiner in his Mogen Avrohom. The Mogen Avrohom cites a passage which is attributed to R. Issac Luria that one should wait to remove the teffilin until after the reading of the torah. Now, asute readers will realize that even according to this, one can still fullfill all the opinions (or close enough) and wait to remove the teffilin until after the torah reading but long before mussaf. However, again, most don't do this, instead they wait until right before mussaf, right at the time R. Fano, no lightweight said one is disrespecting God.
So we now turn to the another passage in the Magen Avraham for the answer. There is a custom to have the teffilin on for 4 kaddashim and 3 keddusot (kedusha in yotzer, kedusah in Shemoneh esreh, and the kedusah of u'va l'tzion). So the question becomes what does one have to do on Rosh Hodesh. Does one need to leave the teffilin on for those kaddashim or because of these other reasons, namely the mussaf can one ignore that requirement on Rosh Hodesh. The Mogen Avrohom says that Rosh Hodesh is different than Hol haMo'ad and on Rosh Hodesh one can not ignore that requirement and therefore one must keep the teffilin on until after the kaddish following u'va l'tzyion.
But here is the issue with the Mogen Avrohom, R. Yeshaya Horowitz (Shelah) holds that really this requirement is switched and one only need 3 kaddashim and 4 kedushot (he counts barakhu as the fourth). So according to him, one has already gotten their three kaddashim after the reading of the Torah.
So to recap, in order for one to require removal of the teffilin right before mussaf one needs to ignore R. Fano (and others who follow him), and ignore R. Horowitz as well.
[As an aside, R. David ben Levi in his Taz says that one need not remove his teffilin at all. R. Joseph Baer Soloveitchik held that if one doesn't have time to wrap them before begining mussaf one should follow the Taz and just say mussaf with them on.]
Sources and further reading: Shu't Rama M'Fano no. 108 (reprinted in Siddur R. Shabtai Sofer, vol. 2 p. 238-39; R. Mordechi Yaffo, Levush, Orakh Hayyim, no. 25 (at the end) and no. 423; R. E. Shapiro, Eliayhu Rabba, Zuta on the Levush; R. Y. Karo, Shulchan Orakh, no. 423:4; R. M. Isserlles Rama, 25:13; Shulchan Orakh Ari"zal, no. 423; R. A. (hamechune Abeli) Gombiner, Mogen Avrohom, no. 25:28; id. at 30; 423:6; R. Nerelanger, Yosef Omets, no. 696; R. J. Kierchheim, Minhagai Vermisia, p. קפג; R. B. Hamburger, Gedoli HaDorot 'al Mishmar Minhagi Ashkenaz, p. 102-03; R. Yom Tov Lippman Heller, Hilchot Teffilin, Ma'adeni Yom Tov. no. 74