Dear R' Avraham,

It's good to hear from you again.

It seems from Rashi that the source is the phrase in the verse, "Avodas Matanah," meaning that anything given to the Kohanim as Matnos Kehunah counts, in its use, as a form of Avodah, and Chazal understand this as referring to the Avodah of the Beis ha'Mikdash. Some note that this implies even though the eating of Korbanos themselves is considered Avodah, since the Kohanim's portion in the offerings is also part of the Matnos Kehunah. Thus, anything given to the Kohanim as Matnos Kehunah carries an element of Avodah, and it is straightforward that this "Avodah" is realized when the gift is used for its purpose. In the case of Terumah, that purpose is its eating.

Kol Tuv,

Aharon Steiner