Ramban mentions it in his letter to the French Sages in defense of Rambam (in 1232). He writes (last line of the page, and continuing from there):
והנני מעיד עלי לפני רבותי שמים וארץ, כי
שמענו ממגידי אמת שבכל ארצות מלכות תימן,
קהלות רבות עוסקים בתורה ובמצות לשמן,
והיו מזכירים שם הרב בכל קדיש וקדיש:
"בחייכון וביומיכון ובחיי דרבנא משה בן
מיימון", אשר האיר עיניהם בתורה, והעמידן
בקרן אורה, לבטל מהן גזרות קשות וכובד
המס, כי היו כטיט חוצות מרמס. ומעליהם עול
מלכות הרים, ויחלו מעט ממשא מלך ושרים
"I call heaven and earth to witness
before [you,] my teachers, on what we have
heard from reliable sources: that in
all areas of the Kingdom of Yemen,
where there are many communities who
are occupied with Torah and mitzvos
for their own sake, they would mention
the name of the Rabbi [Rambam] in
every Kaddish: 'In your lives and in
your days, and in the lifetime of our
teacher Moshe ben Maimon.' He
enlightened their eyes in Torah, and
placed them in a bright situation, by
cancelling for them many serious
decrees and the harshness of taxation
- for they were like trodden down like the mud of the streets. He lifted off
them the yoke of the king, and they
gained some little relief from the
burden of king and princes."
The usual explanation I've seen is that indeed this relates to his having written Iggeres Teiman, although to me it sounds like it's more than that - that he actually interceded for them politically (maybe through Saladin, sultan of Egypt and Syria, whose physician the Rambam was).
If there were reservations about this addition, they're not recorded, as far as I know. In those times the wording of Kaddish may have been a little more fluid anyway. I once perused a manuscript of part of the siddur, dating from the 9th century (in the JTS library), and the Kaddish there is extremely long - it contained requests from Hashem on behalf of the Reish Galusa, the heads of the yeshivos of Sura and Pumbedisa, and a fourth person whose name is illegible (there's a scholarly claim that it was R' Amram Gaon, who according to this view headed a breakaway yeshivah; my personal opinion is that it was simply the local rav or rosh yeshivah of whatever community this manuscript comes from). So there was certainly precedent for such additions, and indeed the Kaddish Derabbanan that we say is sort of a vestige of that.
Ramban describes this usage in the past tense ("היו מזכירים"), so it was probably discontinued when the Yemenite communities received word of the Rambam's passing. Again, if there was any opposition to doing so, it's probably lost to history.
