The hadith you refer to is the following in Jami' At-Tirmidhi:
Adi ibn Hatim narrated: "I came to the Prophet (ﷺ) while I had a cross of gold around my neck. He said: 'O Adi! Remove this idol from yourself!’ And I heard him reciting from Surah Bara’ah: They took their rabbis and monks as lords besides Allah (9:31). He said: ‘As for them, they did not worship them, but when they made something lawful for them, they considered it lawful, and when they made something unlawful for them, they considered it unlawful.’" (Jami’ At-Tirmidhi)
The narrator Adi ibn Hatim is narrating the story about himself. Imam Tirmidhi considered this hadith Ghareeb, and Darussalam grades it as Daeef.
This version is shorter since there is no initial questioning by Adi ibn Hatim. The longer one is quoted in Ibn Kathir’s tafsir for the verse 19:31.
Imam Ahmad, At-Tirmidhi and Ibn Jarir At-Tabari recorded a Hadith via several chains of narration, from Adi bin Hatim, may Allah be pleased with him, who became Christian during the time of Jahiliyyah. When the call of the Messenger of Allah reached his area, Adi ran away to Ash-Sham, and his sister and several of his people were captured. The Messenger of Allah freed his sister and gave her gifts. So she went to her brother and encouraged him to become Muslim and to go to the Messenger of Allah .
Adi, who was one of the chiefs of his people (the tribe of Tai’) and whose father, Hatim At-Ta’i, was known for his generosity, went to Al-Madinah. When the people announced his arrival, Adi went to the Messenger of Allah wearing a silver cross around his neck. The Messenger of Allah recited this Ayah; (They took their rabbis and their monks to be their lords besides Allah).
Adi commented, "I said, `They did not worship them.’"
The Prophet said, "Yes they did. They (rabbis and monks) prohibited the allowed for them (Christians and Jews) and allowed the prohibited, and they obeyed them. This is how they worshipped them."
The Messenger of Allah said to Adi, "O Adi what do you say Did you run away (to Ash-Sham) so that ‘Allahu Akbar’ (Allah is the Great) is not pronounced Do you know of anything greater than Allah What made you run away Did you run away so that `La ilaha illallah’ is not pronounced Do you know of any deity worthy of worship except Allah."
The Messenger invited Adi to embrace Islam, and he embraced Islam and pronounced the Testimony of Truth. The face of the Messenger of Allah beamed with pleasure and he said to Adi, "Verily, the Jews have earned the anger (of Allah) and the Christians are misguided." (Tafsir Ibn Kathir for 9:31)