While Mat and Perrin first mention the colors at the Cleansing, it had been creeping up on them for a while. Mat notes in WH that he has a feeling that he would know if Rand died, and Rand says the same thing about Mat at the end of tPoD. It actually started for him in aCoS when he is waiting to make his secret trip to Caemlyn to meet Bashere and Bael and their women, and IIRC he says he actually first began to notice them as a captive of the Aes Sedai. Like Mat & Perrin, it might have been creeping up on him before that, but the solitude and lack of other things occupying his mind gave him the opportunity to take note of them. In Mat's & Perrin's cases, it was not a lack of anything else allowing them to notice their developing connection to Rand, but rather an event of such supreme significance that it overrode their normal inattention.