Found 2 answers:
Since Challah is a Rabbinic obligation nowadays, the Rabbinic Dimua (as you pointed out) exempts the Rabbinic Challah-obligation.
It's referring to a quantity of dough (without the added Terumah) that is smaller than the amount required to take Challa - the added Terumah (being exempt from Challa) cannot be counted towards the minimum amount, even if it's small enough to be insignificant (Bitul)
Source:
The מלאכת שלמה on the Mishna answers your questions.
He says:
נדמעה עיסתה. באשת כהן מיירי דמדומע ותרומה מותרין לו. ותרומה פטורה מן החלה כדאיתא בספרי:
We are talking about the wife of a Cohen who is permitted to eat Terumah - and Terumah is exempt from Challah, as per the Sifri.
עד שלא גלגלה. ס"א גלגלתה וכן בכולה מתני' בר מדגזבר:
Side note: Since it's Mrs. Cohen, some version have גלגלתה instead of גלגלה except where it's referring to the Gizbar; the fellow in charge of Hekdesh.
שהמדומע פטור. דקסבר חלה בזמן הזה דרבנן ואתי דמוע דרבנן ומפקע חלה דרבנן:
Since Challah is a Rabbinic obligation nowadays, the Rabbinic Dimua (as you pointed out) exempts the Rabbinic Challah-obligation.
The Rambam on the Mishna isn't as explicit but says the same thing:
נדמעה. פירוש שנתערבה בה התרומה וכבר בארנו (תרומות פ"ח מ"ה ולעיל פ"א מ"ד) כי המדומע פטור מן החלה: ואמר תעשה בטהרה ענינו שתגמר כמות שהיא ולא יקפיד בספק טומאה שנולד:
The Yachin also learns it this way:
נדמעה עיסתה
נתערב בה תרומה ואין ק' לבטל ובחלה בזמן הזה מיירי שהוא מדרבנן דאל"כ לא אתא דמוע דרבנן ומפקע חיוב חלה דאוריי':
The Rash MiShantz concurs:
שהמדומע שנדמע לפחות מק' ואתי דימוע דרבנן ומפקעה חלה בזמן הזה דרבנן כדפרשינן לעיל בפ"ק (מ"ד):
He quotes himself from Mishna 1:4 where he says the same thing in more detail and then gives a second answer:
He quotes the Yerushalmi that discusses this questions and concludes that we're talking about a quantity of dough (without the added Terumah) that is smaller than the amount required to take Challa - the added Terumah (being exempt from Challa) cannot be counted towards the minimum amount, even if it's small enough to be insignificant (Bitul)
והמדומע. תרומה שנפלה לפחות מק' חולין אבל נפלה לתוך ק' חולין הכל חולין וחייבין בחלה וטעמא דמדומע משום דתרימו תרומה כתיב ולא שכבר נתרמה וקסבר האי תנא חלה בזמן הזה דרבנן כדאמר בשילהי יוצא דופן דאי מדאורייתא לא אתי דימוע דרבנן ומפקיע חלה דאורייתא ובירושל' (הל' ג) אמרי' כהנא שאל לשמואל לא מסתברא כההן מדומע דתנינן הכא שרובו תרומה אמר ליה אוף אנא סבר כן אלא כד תיסק לארעא דישראל שאל לה כד סליק שמע רב אסי בשם ר' יוחנן אפי' סאה אחת שנפלה לתוך צ"ט חולין ומשמע שם במסקנא דמדומע פטור מן החלה היינו כשאין מן החולין ה' רבעים דאם נתערב סאה תרומה בצ"ט של חולין ולקח מהן ה' רבעים קמח וגלגלן נמצא אחד מק' שבהן תרומה ולכך פטורה מן החלה אבל אם אחר שתסיר אחד מק' נשתיירו עדיין ה' רבעים לפי חשבון תרומה שנתערבה נתחייבת בחלה: