They compiled the clean source using the existing, malicious compiler installation. That compiler had a counter-measure against being recompiled from clean sources; it recognized that situation and perpetrated itself.
(A clean compiler binary might not help; suppose the trick involves other binaries, like the C library. They didn't have the kernel source so it was fairly reasonable to regard the kernel as clean.)