The reason we take off our tefillin before mussaf is
(1) because many say in the kedusha of mussaf, "Kesser Yitnu Lecha", and therefore we need not be wearing the "kesser" of tefillin. (Or I heard once that perhaps it is disrespectful to say "Kesser Yitnu Lecha" while we are wearing our own "crowns" of tefillin.)
(2) Even for those who don't say "kesser etc." in the kedusha, since we try to treat Rosh Chodesh somewhat as a Yom Tov, at least while we say mussaf (which is memorial to the korban mussaf brought in the Bais Hamikdash), we take off our tefillin beforehand.
I have only ever seen people take off their tefillin after kaddish, and it seems this is the proper procedure, since one should have his tefillin on for all the Kaddishes said by the chazzan. Perhaps, though, some people feel they may take them off early as per reason (2).
However, we try not to create a long gap between kaddish and mussaf, and therefore we do not wrap the tefillin until later. In many places, the gabbai or chazzan bang on the amud or bimah to signal everyone to start mussaf, since everyone should begin together.
See Taamei Haminhagim.