Sachverhalt:
A. Mit Eingabe vom 23. Januar 2006 reichte die unter dem Markennamen sunrise auftretende TDC Switzerland AG bei der Eidgenössischen Kommunikationskommission (ComCom) ein gegen die Swisscom Mobile AG gerichtetes Interkonnektionsgesuch ein. Darin beantragte sie primär, die Gebühr für den Interkonnektionsdienst "Swisscom Mobile Terminating Service" (im Wesentlichen: anbieterüberschreitende Verbindungsleistungen bei der Mobiltelefonie) im Hinblick auf deren Höhe und Preisstruktur zu überprüfen und rückwirkend auf den 1. Januar 2006 kostenorientiert festzulegen; zugleich sei die Swisscom Mobile AG zu verpflichten, denselben Dienst nebst einer Verrechnung pro Minute zusätzlich mit einer Verrechnung pro Anruf kostenorientiert anzubieten. Diese Begehren wurden durch verschiedene Eventualanträge ergänzt.
In ihrer Stellungnahme vom 3. März 2006 beantragte die Swisscom Mobile AG, auf das Gesuch nicht einzutreten und eventuell den fraglichen Mobilterminierungspreis auf 20 Rappen pro Minute festzusetzen. Darüber hinaus stellte sie verschiedene prozessuale Begehren: Insbesondere ersuchte sie, über das Eintreten auf das Gesuch sei mit einer selbständig anfechtbaren Verfügung zu entscheiden. Sollte auf das Interkonnektionsgesuch eingetreten werden, sei das Verfahren bis zu einem rechtskräftigen Entscheid über die Frage der Marktbeherrschung in einer hängigen Untersuchung der Wettbewerbskommission zur Terminierung beim Mobilfunk zu sistieren; bei Ablehnung dieses Sistierungsgesuchs sei darüber ebenfalls in einer selbständig anfechtbaren Zwischenverfügung zu befinden.
Mit Zwischenverfügung vom 4. Mai 2006 stellte die Kommunikationskommission fest, sie sei für die Beurteilung des fraglichen Interkonnektionsgesuchs vom 23. Januar 2006 zuständig, und entschied, darauf einzutreten. Gleichzeitig wies sie den Antrag von Swisscom Mobile AG auf Sistierung des Verfahrens ab.
B. Mit Verwaltungsgerichtsbeschwerde vom 15. Mai 2006 an das Bundesgericht beantragt die Swisscom Mobile AG, die Verfügung der Kommunikationskommission vom 4. Mai 2006 sei aufzuheben und auf das Interkonnektionsgesuch der TDC Switzerland AG vom 23. Januar 2006 sei nicht einzutreten. Für den Fall, dass auf das Interkonnektionsgesuch eingetreten werde, sei die Verfügung insoweit aufzuheben, als damit die Sistierung des Verfahrens verweigert wurde, und das Interkonnektionsverfahren sei bis zum rechtskräftigen Entscheid über die Frage der Marktbeherrschung in der hängigen Untersuchung der Wettbewerbskommission zur Terminierung beim Mobilfunk zu sistieren. Darüber hinaus ersucht die Swisscom Mobile AG darum, ihrer Beschwerde die aufschiebende Wirkung zu erteilen.
Die TDC Switzerland AG und die Kommunikationskommission stellen den Antrag, der Verwaltungsgerichtsbeschwerde sei die aufschiebende Wirkung zu verweigern und sie sei in der Sache abzuweisen.
C. Mit verfahrensleitender Verfügung vom 19. Mai 2006 hat der Präsident der II. öffentlichrechtlichen Abteilung des Bundesgerichts im Sinne einer superprovisorischen Massnahme angeordnet, dass bis zum Entscheid über das Gesuch um Erteilung der aufschiebenden Wirkung alle Vollziehungsvorkehren zu unterbleiben haben.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Nach Art. 11 Abs. 1 des Fernmeldegesetzes vom 30. April 1997 (FMG; SR 784.10) müssen marktbeherrschende Anbieterinnen von Fernmeldediensten andern Anbieterinnen nach den Grundsätzen einer transparenten und kostenorientierten Preisgestaltung auf nichtdiskriminierende Weise Interkonnektion gewähren, wobei sie die Bedingungen und Preise für ihre einzelnen Interkonnektionsdienstleistungen gesondert auszuweisen haben.
Grundsätzlich werden die Bedingungen der Interkonnektion zwischen den beteiligten Unternehmungen direkt vereinbart. Eine behördliche Regelung ist gesetzlich nur subsidiär für den Fall vorgesehen, dass sich die Parteien nicht innert vernünftiger Frist einigen können. Gemäss <ref-law> verfügt die Eidgenössische Kommunikationskommission auf Antrag des Bundesamtes für Kommunikation die Interkonnektionsbedingungen nach markt- und branchenüblichen Grundsätzen, wenn innert drei Monaten zwischen dem zur Interkonnektion verpflichteten Anbieter und dem Anfrager keine Einigung zustande kommt (vgl. <ref-ruling> E. 2.1 S. 50; <ref-ruling> E. 1.2 S. 16, mit Hinweisen).
1.2 Die vorliegende Verwaltungsgerichtsbeschwerde richtet sich gegen einen Zwischenentscheid. Gemäss Art. 101 lit. a OG (e contrario) sind Zwischenverfügungen nur dann selbständig mit Verwaltungsgerichtsbeschwerde anfechtbar, wenn dieses Rechtsmittel auch gegen den Endentscheid offen steht. Verfügungen über die Zuständigkeit und die Sistierung eines Verfahrens gelten grundsätzlich als selbständig anfechtbar (vgl. Art. 45 Abs. 2 lit. a und c VwVG). Vorliegend erscheint allerdings fraglich, ob ein eigentlicher Zuständigkeitskonflikt besteht oder nicht eher über eine sonstige Prozessvoraussetzung gestritten wird. So oder so ist jedoch erforderlich, dass die Zwischenverfügung einen nicht wieder gutzumachenden Nachteil bewirken kann, wobei dieser Nachteil nicht rechtlicher Natur zu sein braucht, sondern ein (qualifiziertes) tatsächliches, insbesondere wirtschaftliches Interesse dafür genügt (Art. 97 OG in Verbindung mit Art. 5 und 45 Abs. 1 VwVG; <ref-ruling> E. 2a S. 136; <ref-ruling> E. 2a S. 619).
Endverfügungen der Kommunikationskommission in Anwendung von <ref-law> unterliegen der Verwaltungsgerichtsbeschwerde an das Bundesgericht (vgl. Art. 11 Abs. 4 und Art. 61 Abs. 1 FMG; <ref-ruling> E. 1.1 S. 49; <ref-ruling> E. 1.3, je mit Hinweisen). Im vorliegenden Fall geht es in der Sache um den Mobilterminierungspreis der Beschwerdeführerin im Verhältnis zur Beschwerdegegnerin, d.h. um den Preis, den diese jener für die Verbindung eines Anrufs aus ihrem Netz mit demjenigen der Beschwerdeführerin zu bezahlen hat. Der angefochtene Entscheid, mit dem die Kommunikationskommission auf das Interkonnektionsgesuch der Beschwerdegegnerin eintritt und die Sistierung des Verfahrens ablehnt, hat für die Beschwerdeführerin weitreichende Folgen. Es steht ein umfangreiches Verfahren an, in dem unter anderem die Frage beantwortet werden muss, ob die Beschwerdeführerin den schweizerischen Mobiltelefoniemarkt beherrscht; gleichzeitig ist mit Blick auf die gegebenenfalls erforderliche kostenorientierte Preisgestaltung die Kostenstruktur bei der Beschwerdeführerin abzuklären, wobei diese dafür grundsätzlich den Nachweis zu erbringen hat (vgl. Art. 58 Abs. 3 der Verordnung vom 31. Oktober 2001 über Fernmeldedienste, FDV; SR 784.101.1). Die der Beschwerdeführerin entstandenen Aufwendungen würden ihr auch im Falle des Obsiegens in der Hauptsache nicht vergütet, weil die Zusprechung einer Parteientschädigung im erstinstanzlichen Interkonnektionsverfahren mangels gesetzlicher Grundlage ausgeschlossen ist (<ref-ruling> E. 5 S. 61 ff.). Der angefochtene Zwischenentscheid bewirkt damit einen nicht wieder gutzumachenden Nachteil für die Beschwerdeführerin, weshalb sich die Verwaltungsgerichtsbeschwerde als zulässig erweist.
1.3 Mit Verwaltungsgerichtsbeschwerde können die Verletzung von Bundesrecht, einschliesslich Überschreitung oder Missbrauch des Ermessens, sowie die unrichtige oder unvollständige Feststellung des rechtserheblichen Sachverhaltes gerügt werden (Art. 104 lit. a und b OG). Nicht überprüfen kann das Bundesgericht die Angemessenheit des angefochtenen Entscheides (Art. 104 lit. c OG e contrario). Da es sich bei der Kommunikationskommission nicht um eine richterliche Behörde handelt, greift die Kognitionsbeschränkung von Art. 105 Abs. 2 OG nicht (<ref-ruling> E. 1.2 S. 49; <ref-ruling> E. 3.1-3.3 S. 18 ff.).
2. 2.1 Die Beschwerdeführerin macht zunächst geltend, ihr Mobilterminierungspreis sei nie Gegenstand von Verhandlungen mit der Beschwerdegegnerin gewesen und diese habe es versäumt, von der Beschwerdeführerin innert der vertraglich vorgesehenen Frist und in der erforderlichen Form eine Preisanpassung zu verlangen. Dem regulatorischen behördlichen Eingriff stünden die Grundsätze der Vertragsfreiheit und des Verhandlungsprimats entgegen, wie sie aus <ref-law> hervorgingen. Die Kommunikationskommission sei somit sachlich nicht zuständig, die Interkonnektionsbedingungen zu verfügen.
Die Vorinstanz geht demgegenüber davon aus, es könne aus den vorliegenden Beweismitteln nicht zweifelsfrei geschlossen werden, ob bzw. in welchem Umfang über den Mobilterminierungspreis der Beschwerdeführerin ausdrücklich verhandelt worden sei. Sie führt jedoch aus, bei der Interkonnektion unter Einschluss der Mobilterminierung handle es sich um ein doppelt synallagmatisches Vertragsverhältnis und Netzzusammenschaltungen würden in der Praxis mit in sich geschlossenen Vertragswerken geregelt. Da die Parteien unbestrittenermassen Verhandlungen über die Mobilterminierungspreise der Beschwerdegegnerin geführt hätten, sei aufgrund der Wechselseitigkeit der Preise davon auszugehen, dass auch die entsprechenden Preise der Beschwerdeführerin Verhandlungsgegenstand gebildet hätten.
2.2 Nach <ref-law> verfügt die Kommunikationskommission die Interkonnektionsbedingungen, wenn innert drei Monaten bei den dafür gesetzlich vorgeschriebenen Verhandlungen zwischen dem zur Interkonnektion verpflichteten Anbieter und dem Anfrager keine Einigung zustande kommt. Die um Interkonnektion nachsuchende Anbieterin kann dem Bundesamt für Kommunikation (als instruierende und antragstellende Behörde) zu Beweiszwecken die Aufnahme von Interkonnektionsverhandlungen oder von Neuverhandlungen schriftlich mitteilen (so genannte Notifikation der Verhandlungsaufnahme; <ref-law>). Anzuzeigen ist lediglich die Aufnahme von Verhandlungen. Über den Inhalt braucht nichts mitgeteilt zu werden.
2.3 Entgegen der Auffassung der Beschwerdeführerin steht die sachliche Zuständigkeit der Vorinstanz (im Sinne von <ref-law>) nicht in Frage. Sie ist die sachlich kompetente Behörde, die im Streitfall über Interkonnektionsbedingungen entscheidet. Bei der vorgeschriebenen Verhandlungsfrist von drei Monaten handelt es sich um eine eigenständige spezialgesetzliche Prozess- bzw. Eintretensvoraussetzung. Diese Voraussetzung muss erfüllt sein, damit die Kommunikationskommission die Interkonnektionsbedingungen hoheitlich festlegen darf. Wird die Frist von drei Monaten nicht eingehalten, ist ein regulatorisches Verfahren ausgeschlossen und damit unzulässig.
2.4 Interkonnektion erfolgt selten einseitig. Inhaltlich geht es in aller Regel um eine Zusammenschaltung von Fernmeldenetzen, die mit dem Austausch von Fernmeldeleistungen verbunden ist. Das Interkonnektionsverhältnis zwischen zwei Anbieterinnen wird denn auch üblicherweise als ein einziges Vertragsverhältnis erachtet bzw. durch ein in sich geschlossenes Vertragswerk geregelt. Entscheidend ist letztlich die Wechselseitigkeit des Interkonnektionsverhältnisses (vgl. das zur Publikation vorgesehene Urteil des Bundesgerichts 2A.450/2005 und 2A.452/2005 vom 21. April 2006, E. 7.2).
Im vorliegenden Fall geht es um die Interkonnektionsbedingungen bei der Mobilterminierung zwischen zwei Anbieterinnen von Mobiltelefoniediensten, die im entsprechenden schweizerischen Markt eine wesentliche Rolle spielen und die auf die wechselseitigen Verbindungen angewiesen sind. Die Beschwerdeführerin kann sich demnach nicht darauf berufen, über die Bedingungen für ihre eigenen Interkonnektionsleistungen hätten zwischen den Parteien nie Verhandlungen stattgefunden. Es ist unbestritten, dass die Beschwerdeführerin mit Schreiben vom 28. Juli 2005 die Beschwerdegegnerin ersuchte, ihren Mobilterminierungspreis per 1. Januar 2006 auf dasselbe Preisniveau wie dasjenige der Beschwerdeführerin zu senken. Diese Verhandlungsaufnahme wurde dem Bundesamt für Kommunikation mit der Zustellung einer Kopie des Schreibens notifiziert. Aufgrund der einheitlichen Betrachtungsweise muss somit davon ausgegangen werden, dass die Interkonnektionsverhandlungen stattgefunden und auch die reziproken Mobilterminierungspreise der Beschwerdeführerin als potentiellen Gegenstand mitumfasst haben, selbst wenn die Parteien über die letzteren eventuell noch nicht ausdrücklich verhandelten (vgl. dazu das zur Publikation bestimmte Urteil des Bundesgerichts 2A.450/2005 und 2A.452/2005 vom 21. April 2006, E. 7.3).
2.5 An dieser Rechtslage ändert auch der vertragliche Preisanpassungsmechanismus nichts, der Änderungen per Ende Jahr unter Einhaltung einer dreimonatigen Ankündigungsfrist vorsieht. Zunächst erscheint fraglich, ob ein vertragliches Anpassungsgesuch in jedem Fall überhaupt mit Verhandlungen im Sinne von <ref-law> gleichgesetzt bzw. ob auf vertraglicher Grundlage die gesetzliche Prozessvoraussetzung von <ref-law> geändert werden kann. So oder so müsste aber in einem wechselseitigen Interkonnektionsverhältnis auch der vertragliche Anpassungsmechanismus so ausgestaltet sein bzw. ausgelegt werden, dass durch das Gesuch um Preisanpassung durch die eine Partei die Preise beider Parteien zum Verhandlungsgegenstand würden. Nur so liesse sich die vertragliche Regelung allenfalls mit dem Gesetz in Einklang bringen.
2.6 Bildete der Mobilterminierungspreis der Beschwerdeführerin somit Gegenstand der mehr als dreimonatigen Verhandlungen, verletzte die Vorinstanz Bundesrecht nicht, indem sie auf das Interkonnektionsgesuch der Beschwerdegegnerin eintrat.
3. 3.1 Was die von der Beschwerdeführerin angestrebte Sistierung des Interkonnektionsverfahrens betrifft, beruft sich diese im Wesentlichen darauf, die Wettbewerbskommission führe gegenwärtig eine Untersuchung über die Frage der Marktbeherrschung bei der Mobilfunkterminierung durch. Zwecks Koordination des Interkonnektionsverfahrens mit dem wettbewerbsrechtlichen Verfahren sei das erste daher zu sistieren.
3.2 Die Sistierung eines Verfahrens gilt grundsätzlich als rechtmässig, wenn sie sich als sachlich gerechtfertigt erweist. Dies trifft insbesondere dann zu, wenn dem Ausgang eines anderen Verfahrens für den Entscheid im eingestellten Prozess eine wesentliche präjudizielle Bedeutung zukommt (vgl. <ref-ruling> E. 2b S. 3; <ref-ruling> E. 3e S. 217, mit Hinweis). Sprechen sachliche Gründe gegen eine Sistierung, ist umgekehrt eine Verweigerung derselben selbst dann nicht bundesrechtswidrig, wenn ein paralleles Verfahren läuft.
3.3 Gemäss der bundesgerichtlichen Rechtsprechung gelangt das sektorielle Interkonnektionsregime neben dem allgemeinen Wettbewerbsrecht zur Anwendung (Urteil des Bundesgerichts 2A.503/2000 und 2A.505/2000 vom 3. Oktober 2001 [so genannter Commcare-Entscheid; vgl. ZBl 103/2002 S. 244], E. 6c). Die Konsultation der Wettbewerbskommission im Interkonnektionsverfahren soll eine gewisse inhaltliche Koordination der beiden Verfahren sicherstellen (BBl 1996 III 1427). Abgesehen vom gemeinsamen Anknüpfungspunkt der Marktbeherrschung handelt es sich jedoch um zwei verschiedene Verfahren. Dabei hat nicht grundsätzlich das wettbewerbsrechtliche dem interkonnektionsrechtlichen vorzugehen. Vielmehr ist unabhängig von der Abfolge davon auszugehen, dass die involvierten Behörden die Analyse der Marktbeherrschung aufeinander abstimmen. In der Regel wird sich dabei die untere Instanz an der Rechtsprechung der höheren ausrichten.
Ob ein erstinstanzlicher Entscheid in der Untersuchung der Wettbewerbskommission kurz bevorsteht, ist unklar. Je nach Verfahrensgang kann dies unter Umständen noch lange dauern. Möglich ist auch, dass die Frage der Marktbeherrschung in den kartellrechtlichen Untersuchungen offen bleibt, etwa weil ohnehin kein missbräuchliches Verhalten vorliegt. Ebenso wenig kann eine Priorität des wettbewerbsrechtlichen Verfahrens aus den unterschiedlichen Rechtsmittelwegen abgeleitet werden. Eine kartellrechtliche Verfügung der Wettbewerbskommission lässt sich zunächst bei der Rekurskommission für Wettbewerbsfragen (vgl. Art. 44 des Bundesgesetzes vom 6. Oktober 1995 über Kartelle und andere Wettbewerbsbeschränkungen, Kartellgesetz, KG; SR 251) und deren Entscheid (in Anwendung von Art. 97 Abs. 1 i.V.m. Art. 98 lit. e OG) mit Verwaltungsgerichtsbeschwerde beim Bundesgericht anfechten. Gegen den interkonnektionsrechtlichen Entscheid der Kommunikationskommission kann demgegenüber einzig direkt beim Bundesgericht Verwaltungsgerichtsbeschwerde erhoben werden (vgl. E. 1.2). Das Interesse an einer beschleunigten höchstrichterlichen Beantwortung der Frage der Marktbeherrschung würde insofern sogar eher für einen Vorrang des Interkonnektionsverfahrens sprechen. Weder in der einen noch in der anderen Richtung ergibt sich hieraus jedoch eine allgemeingültige Priorität. In beiden Verfahren bleibt der Rechtsschutz so oder so unabhängig davon garantiert, ob im einen oder anderen Verfahren eine Sistierung angeordnet wird oder nicht. Auch durch das gesetzliche Koordinationsziel wird der Rechtsschutz nicht beschnitten; vielmehr dient dieses gerade einer einheitlichen und damit in sich geschlossenen Praxis.
Entscheidend ist indes, dass Interkonnektion letztlich die Beseitigung des Wettbewerbsvorteils bezweckt, über den die pflichtige Anbieterin nur deshalb verfügt, weil sie den fraglichen Bereich des Telekommunikationsmarkts beherrscht. Die Rechtsordnung versucht zu simulieren, dass die zwischen den konkurrierenden Anbieterinnen von Fernmeldedienstleistungen geltenden Interkonnektionsbedingungen unter funktionierenden Wettbewerbsverhältnissen zustande kommen. Von dieser Wettbewerbssituation sollen am Ende der Telekommunikationsmarkt als Ganzes und insbesondere die Endkunden der Fernmeldediensteanbieterinnen profitieren (zur Publikation bestimmtes Urteil des Bundesgerichts 2A.450/2005 und 2A.452/2005 vom 21. April 2006, E. 2.3.1). Selbst wenn zwischen den Fernmeldediensteanbieterinnen finanzielle Ausgleichszahlungen auch noch nachträglich stattfinden können, profitieren die Endkunden erst und nur dann von günstigeren Tarifen, wenn die interkonnektionsrechtlich bedingte Verbilligung der Preise tatsächlich festgelegt ist und Anwendung findet. Das begründet ein erhebliches öffentliches Interesse an einer beförderlichen Erledigung des Interkonnektionsverfahrens.
3.4 Im vorliegenden Fall ist die Interkonnektion als solche (in technischer Hinsicht) an sich nicht in Frage gestellt. Das Interkonnektionsverfahren zu sistieren brächte aber ein erhebliches Risiko der Verzögerung der Einführung der allenfalls verbilligten Preise mit sich. Die damit verbundenen öffentlichen Interessen vermögen zwar nicht unbedingt die Notwendigkeit vorsorglicher Massnahmen zu begründen (vgl. <ref-ruling>, insbes. E. 4c S. 139), sprechen aber deutlich gegen eine Sistierung des Hauptverfahrens. Die Beschwerdeführerin macht keine überzeugenden Gründe geltend, die zu einer anderen Beurteilung führen könnten. Die mit dem angefochtenen Entscheid verfügte Verweigerung der Sistierung des Interkonnektionsverfahrens lässt sich daher sachlich rechtfertigen und verstösst nicht gegen Bundesrecht.
4. 4.1 Die Verwaltungsgerichtsbeschwerde erweist sich als unbegründet und ist abzuweisen.
4.2 Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten der Beschwerdeführerin aufzuerlegen (Art. 156 Abs. 1, Art. 153 und 153a OG). Da die Beschwerdegegnerin durch interne Mitarbeiter vertreten wird, ist praxisgemäss von der Zusprechung einer Parteientschädigung für das bundesgerichtliche Verfahren abzusehen (vgl. dazu das Urteil 2A.191/2005 vom 2. September 2005, E. 6).
4.3 Mit dem Entscheid in der Sache wird das Gesuch um Erteilung der aufschiebenden Wirkung gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 4'000.-- wird der Beschwerdeführerin auferlegt.
3. Eine Parteientschädigung wird nicht zugesprochen.
4. Dieses Urteil wird den Parteien und der Eidgenössischen Kommunikationskommission (ComCom) schriftlich mitgeteilt.
Lausanne, 12. Juli 2006
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: