He did the farewell tawaf, and after he finished he noticed traces of impurity on his clothes

Firstly: 

The scholars (may Allah have mercy on them) differed as to whether or not it is stipulated that impurities must be removed in order for tawaf to be valid. 

The majority are of the view that this is stipulated. The Hanafis are of the view that it is not stipulated. 

An-Nawawi (may Allah have mercy on him) said in al-Majmoo‘ (8/23): We have stated that our view is that it is essential to be in a state of purity and with wudu, and one’s clothes and body should be free of any impure substance. This is the view of Maalik, and it was narrated by al-Maawirdi from the majority of scholars, and it was narrated by Ibn al-Mundhir from the majority of scholars that one should be in a state of purity and have wudu. Only Abu Haneefah stated that having wudu and being free of any impure substance is not an essential condition for tawaf, so if a person does tawaf and he has some impure substance on him, or he is in a state of minor impurity or is junub, his tawaf is still valid. End quote.

See: al-Mughni (3/186) 

Secondly: 

If a person circumambulates the Ka‘bah, then after finishing tawaf he realises that some impure substance on him, whether the impure substance was on his clothes or his body, his tawaf is valid  and he does not have to do anything further, because of the hadith of Abu Sa‘eed which we will quote below. 

Ibn Qudaamah (may Allah have mercy on him) said in al-Kaafi (1/510): It was narrated from him – i.e., Imam Ahmad – concerning one who does tawaf az-ziyaarah (tawaf al-ifaadah) and forgets about making sure that he is in a state of purity until he leaves. His Hajj is acceptable and he does not have to do anything further. This indicates that this requirement is waived if one forgets.… The same applies to being free of any impure substance because it is an act of worship in which it is not stipulated that one should face the qiblah, so that is not stipulated in this case, as in the case of sa‘i and standing in ‘Arafah. End quote. 

Ibn ‘Uthaymeen (may Allah have mercy on him) said in Sharh al-Kaafi: 

If we assume that a person did tawaf in an izaar that was contaminated with an impure substance, he does not have to repeat it. If he had forgotten or was unaware of that, then the matter is clear. But if he did it deliberately, there is no evidence to indicate that. End quote. 

The fuqaha’ (may Allah have mercy on them) discuss this matter in detail in their chapters on the prayer, and they stated that if a person prays in an impure garment, but he does not realise that it is impure until after he has finished his prayer, then his prayer is valid. The same may be said with regard to tawaf. If a person does tawaf, then after finishing tawaf he realises that his garment was impure, his tawaf is valid according to the majority of scholars. 

An-Nawawi said in al-Majmoo‘ (3/163): 

Chapter: According to scholarly views concerning the one who prays with some impure substance on him, because he forgot about it or was unaware of it. We have stated that the most correct view in our opinion is that he must repeat it. This was stated by Abu Qilaabah and Ahmad. But the majority of scholars said that he does not have to repeat it. This was narrated by Ibn al-Mundhir from Ibn ‘Umar, Ibn al-Musayyab, Tawoos, ‘Ata’, Saalim ibn ‘Abdullah, Mujaahid, ash-Shu‘bi, an-Nakha‘i, az-Zuhri, Yahya al-Ansaari, al-Awzaa‘i, Is-haaq and Abu Thawr. Ibn al-Mundhir said: This is also my view, and it is the view of Rabee‘ah and Maalik. There is strong evidence for this view, and it is the favoured view. End quote. 

This view is supported by the report narrated by Abu Sa‘eed (may Allah be pleased with him) who said: Whilst the Messenger of Allah (blessings and peace of Allah be upon him) was leading his companions in prayer, he took off his sandals and placed them to his left. When the people saw that, they also took off their sandals. When the Messenger of Allah (blessings and peace of Allah be upon him) finished his prayer, he said: “What made you take off your sandals?” They said: We saw you take off your sandals, so we took off our sandals. The Messenger of Allah (blessings and peace of Allah be upon him) said: “Jibreel (blessings and peace of Allah be upon him) came to me and told me that there was some dirt on them. When one of you comes to the mosque, let him look, and if he sees any dirt on his sandals, let him wipe it off and pray wearing them.” Narrated by Abu Dawood (650). Classed as saheeh by Shaykh al-Albaani in Saheeh Abi Dawood (3/221) 

If the prayer was rendered invalid by impurity of which the worshipper was unaware, the Prophet (blessings and peace of Allah be upon him) would have repeated his prayer. But because he did not repeat it, this indicates that prayer is not rendered invalid in the case of impurity, if the worshipper is unaware of its presence or forgot about it. The same may be said with regard to tawaf. 

Conclusion: 

Your tawaf is valid, whether your garment became impure during it or that happened afterwards. 

And Allah knows best.