the Kheloy Yaakov in R'H siman 20 proves eidues shey ata yachol lehazeima is meacev also in kiddush hachodesh, from tosfos in Kesovos 20a that explains the halacha of ein ed naasa dayan is because that way it is eidus shey ata yachol lehazima. Since ein eid naasa dayan also in kiddush hachodesh, we see from tosfos eidua shey ata yachol lehazima is passul by kiddush hachodes.
You probably mean תוספות כתובות כ"א עמוד ב' ד"ה אין עד.
I don’t know who the “Kheloy Yaakov” is (misspelling?), but I suppose he is basing himself on the יש מפרשים in that Tosfos. If that is the case, I refer you to Beis Halevi (3:6:4 – here is a
link) who learns Tosfos differently. In a nutshell, he says that there is clearly no דין הזמה by קידוש החודש. Therefore, the פשט in Tosfos is that because there is the כלל of אין עד נעשה דיין (based on the דין הזמה) by דיני נפשות ודיני ממונות, therefore, by קידוש החדש there is also the דין of אין עד נעשה דיין. The reason for this is that we have to make equal דיני העדויות as much as possible (based on the פסוק of משפט אחד יהיה לכם), unless there is a clear גזירת הכתוב to the contrary. There is a גזירת הכתוב saying that there is no דין הזמה by קידוש החודש, however, there is no such גזירת הכתוב with regards to the כלל of אין עד נעשה דיין.
In short, there
is a דין of אין עד נעשה דיין by קידוש החדש (which is derived בעלמא from עדות שאתה יכול להזימה), but there
is not a דין of עדות שאתה יכול להזימה by קידוש החדש.
Also what u quote from R Shmuel that eidus shey ata yachol lehazima is based on being mevatel there eidus, is basically a rashi in Sanhderin 40a. However, this would still not answer the rebbes question, as in his case the eidus would not be void due to the eidim being muzamim, rather due to them being passul leidus. Even though we used hazomo to arrive at that conclusion, since we now know they are not eidem at all, they are eidem zommim, and the process was thus not a genuine hazomo. So even according to Rashis opinion it is lechorah an eidus shey ata yachol lehzsima.
Again, Reb Shmuel says (did you look it up?) that the דין הזמה itself carries within it two ענינים, one is that the עדות becomes בטל, second that there is the עונש of הזמה. The דין of עדות שאתה יכול להזימה is only regarding the first detail, not the second.
Now, in our case, the fact that Kat Alef were פסול לעשות at the time that they were מעיד is irrelevant to the first detail, and is relevant only to the second. Therefore, it is considered עדות שאתה יכול להזימה. [And I don't see how the מראה מקום to רש"י in סנהדרין is relevant.]
P.S. I hope the readers don’t mind the Hebrew type, it is just easier to do it that way, then to figure out how to spell it in English. [I imagine anyone reading this thread would not be the type to mind.]