I don't think that the emphasis here is on Yisrael vs. Nochri. The Mishnah said "Kol Adam" meaning from Yisrael, as Nochrim are never fit for testimony. The Rambam's intent by saying "from Yisrael," is apparent from the context in Mishnah Torah: "Originally they would accept testimony from every man from Israel, as all Jews have a status of being Kosher until you know that he is unfit." The Rambam is explaining that they indeed would accept testimony from any Jewish man, even though they did not know whether or not he was an upstanding Jew or not. One might otherwise have thought "Kol Adam" meant any man whom they knew for certain that he was not a thief, or had any other character blemish that might make him unfit for testimony (besides wanting to mess up the Jewish calendar).

All the best,

Yaakov Montrose