Sachverhalt:
A. Am 29. Mai 1998 erteilte die Eidgenössische Kommunikationskommission (ComCom) der Rechtsvorgängerin der heutigen TDC Switzerland AG, die unter dem Markennamen sunrise auftritt, eine Konzession zur Erbringung von Mobilfunkdiensten in der Schweiz (Konzession Nr. 25100002). Diese wurde am 21. Dezember 2000, mit Wirkung ab dem 1. Januar 2001, durch eine neue Konzession abgelöst (neue Konzession Nr. 25100002). Die Konzession umfasst die Befugnis zur Erbringung von Mobilfunkdiensten über ein landesweites digitales zellulares Netz unter Nutzung des Frequenzspektrums in den Frequenzbändern 900 MHz und 1'800 MHz auf der Grundlage des GSM-Standards (GSM = Global System for Mobile Communications).
B. Im Jahr 2003 kündigte das Bundesamt für Kommunikation an, künftig die Verwaltungsgebühren für Mobilfunkdienste (GSM und UMTS) um 85 % zu senken und gleichzeitig die Funkkonzessionsgebühren im Bereich GSM um 108 % zu erhöhen. Mit Schreiben vom 16. Februar 2004 teilte die TDC Switzerland AG dem Bundesamt mit, sie lehne die Erhöhung der GSM-Funkkonzessionsgebühren ab. Am 18. März 2004 verfügte das Bundesamt, gestützt auf die in der Zwischenzeit per 1. Januar 2004 geänderten Verordnungsbestimmungen, den jährlichen technischen Netzbeschrieb (Anhang III zur GSM-Konzession der TDC Switzerland AG). Darin legte es die Gebühren für das Jahr 2004 auf Fr. 3'560'000.-- fest, wobei sich dieser Betrag aus einer Konzessionsgebühr von Fr. 3'344'640.-- und einer Verwaltungsgebühr von Fr. 215'360.-- zusammensetzte.
C. Dagegen führte die TDC Switzerland AG im Hinblick auf die festgesetzten Konzessionsgebühren Beschwerde bei der Rekurskommission für Infrastruktur und Umwelt (REKO INUM, nachfolgend: Rekurskommission INUM). Diese hiess die Beschwerde am 10. Februar 2005 gut, änderte die angefochtene Verfügung in den einschlägigen Dispositivteilen im Sinne der Erwägungen ab und setzte die Konzessionsgebühren auf Fr. 1'608'000.-- fest. Zur Begründung wurde im Wesentlichen ausgeführt, die Verordnungsbestimmung, auf welche sich die Erhöhung der Konzessionsgebühr stütze, verfüge im Gesetz über keine genügende Grundlage, da die neue Berechnung der Gebührenhöhe massgeblich auf dem Marktwert der GSM-Konzession beruhe, was im Gesetz als Kriterium nicht vorgesehen sei; überdies zähle die Höhe der Gebühr zu den mit der Konzession eingeräumten wohlerworbenen Rechten und lasse die Konzessionsurkunde die strittige Erhöhung nicht zu. Die Konzessionsgebühr sei daher weiterhin auf der Grundlage der alten Verordnungsbestimmung zu berechnen.
D. Mit Verwaltungsgerichtsbeschwerde vom 14. März 2005 beantragt das Eidgenössische Departement für Umwelt, Verkehr, Energie und Kommunikation die Aufhebung des Entscheides der Rekurskommission INUM vom 10. Februar 2005, wobei es sich insbesondere darauf beruft, die fragliche Verordnungsrevision finde im Gesetz eine genügende Grundlage und die Konzessionsurkunde behalte Änderungen der einschlägigen Rechtsnormen ausdrücklich vor.
Die TDC Switzerland AG schliesst auf Abweisung der Beschwerde; eventuell sei das Departement im Rahmen eines zweiten Schriftenwechsels aufzufordern, offen zu legen, wie es den Wert der Konzession berechne, woraufhin wiederum der TDC Switzerland die Gelegenheit einzuräumen sei, sich zu dieser Bewertung vernehmen zu lassen. Die Rekurskommission INUM stellt ebenfalls den Antrag, die Beschwerde sei abzuweisen.

Das Bundesgericht zieht in Erwägung:
1. Gemäss Art. 61 Abs. 2 und 3 des Fernmeldegesetzes vom 30. April 1997 (FMG; SR 784.10) in Verbindung mit Art. 97 ff. OG unterliegen Entscheide der Rekurskommission INUM in Anwendung des Fernmeldegesetzes der Verwaltungsgerichtsbeschwerde an das Bundesgericht. Dabei ist das in der Sache zuständige Departement für Umwelt, Verkehr, Energie und Kommunikation gemäss Art. 103 lit. b OG zur Beschwerdeführung berechtigt (vgl. das Urteil des Bundesgerichts 2A.426/2005 vom 30. August 2005, E. 1).
2. 2.1 Nach <ref-law> erhebt die Konzessionsbehörde für Funkkonzessionen eine Konzessionsgebühr. Die Höhe der Gebühr bemisst sich dabei für Konzessionen, die nicht im Versteigerungsverfahren vergeben werden, nach den folgenden Kriterien (<ref-law>): dem zugeteilten Frequenzbereich und der Frequenzklasse (lit. a), der zugeteilten Bandbreite (lit. b), der räumlichen Ausdehnung (lit. c) und der zeitlichen Nutzung (lit. d). Bei versteigerten Funkkonzessionen entspricht die Konzessionsgebühr dem angebotenen Betrag abzüglich der Verwaltungsgebühr (<ref-law>).
2.2 Die beiden der Beschwerdegegnerin erteilten Mobilfunkkonzessionen werden ergänzt durch verschiedene Anhänge, welche die Einzelheiten regeln. Darunter befindet sich der so genannte technische Netzbeschrieb, der jedes Jahr neu verfügt wird und insbesondere Regeln für die Frequenzen und die Nutzung sowie Angaben über den Aufbau und die Installation des Funknetzes enthält und schliesslich die zu erhebenden Verwaltungsgebühren festsetzt. Konzessionsgebühren für die Nutzung des Frequenzspektrums werden bei der UMTS-Konzession nicht erhoben, da diese bereits mit der Auktionsgebühr für die gesamte Konzessionsdauer abgegolten wurden. Hingegen ist die hier strittige jährlich zu erhebende Konzessionsgebühr für die GSM-Konzession jeweils zusammen mit und auf der Grundlage des technischen Netzbeschriebs festzulegen (Ziff. 5.1.2 der Konzession Nr. 25100002).
Zuständig für die Erhebung der Konzessionsgebühr ist an sich die Konzessionsbehörde, d.h. die Kommunikationskommission (vgl. Art. 39 Abs. 1 i.V.m. <ref-law>). Diese kann allerdings einzelne Aufgaben dem Bundesamt für Kommunikation übertragen (<ref-law>). Die Kommunikationskommission hat ihre Kompetenz zur Erhebung von Konzessionsgebühren nicht rechtssatzmässig abgetreten; jedenfalls findet sich weder in der Verordnung der Eidgenössischen Kommunikationskommission betreffend das Fernmeldegesetz vom 17. November 1997 (SR 784.101.112) noch im Geschäftsreglement der Kommunikationskommission (SR 784.101.115) eine entsprechende Kompetenzdelegation. Art. 8 Abs. 1 des zweitgenannten Erlasses sieht immerhin unter anderem vor, dass das Bundesamt die Entscheide der Kommunikationskommission vollzieht. Die jährliche Festsetzung des technischen Netzbeschriebs stellt in diesem Sinne eine Vollzugshandlung dar. Indem die Kommunikationskommission in der Konzession die Bestimmung der jährlichen Konzessionsgebühr mit dem technischen Netzbeschrieb verknüpfte, hat sie damit wenigstens sinngemäss auch die Kompetenz zur Festsetzung der Konzessionsgebühr dem Bundesamt übertragen. Obwohl eine entsprechende deutlichere Delegation wünschbar erscheint, wird die Zuständigkeit des Bundesamts im Übrigen von keiner Seite in Frage gestellt.
2.3 Nach Art. 9 der Verordnung vom 6. Oktober 1997 über Gebühren im Fernmeldebereich (GFV; SR 784.106) in der Fassung vom 5. Dezember 2003 (AS 2003 4777) beträgt die Konzessionsgebühr pro zugeteilte Hochfrequenzbandbreite bis zu 25 kHz jährlich Fr. 1560.-- (Abs. 1). Für ein Vielfaches der zugeteilten Hochfrequenzbandbreite von 25 kHz werden die Konzessionsgebühren mit demselben Vielfachen multipliziert (Abs. 3). Gemäss der alten Fassung von Art. 9 Abs. 1 und 3 GFV vom 6. Oktober 1997 waren für die entsprechende Konzessionsgebühr jährlich Fr. 1'500.-- pro zugeteilten Funkfrequenzkanal mit einer Hochfrequenzbandbreite bis zu 25 kHz zu erheben, gegebenenfalls multiplizierbar mit dem Vielfachen der Hochfrequenzbandbreite von 25 kHz (AS 1997 2897).
In Anwendung von Art. 9 GFV errechnete das Bundesamt für die GSM-Konzession der Beschwerdegegnerin des Jahres 2004 eine Konzessionsgebühr von Fr. 3'344'640.--, indem es von 134 Kanälen von 200 kHz landesweit ausging und diese mit Fr. 1'560.-- für 16 Hochfrequenzbandbreiten bis zu 25 kHz pro Kanal multiplizierte; dabei zählte sie, gestützt auf den veränderten Wortlaut der neuen Verordnungsbestimmung, den Empfang und das Senden pro Kanal (so genannte "up- und downlink-Frequenzen") separat, womit sie auf 16 statt acht Bandbreiten von 25 kHz pro 200 kHz kam. Im Ergebnis rechnete das Bundesamt somit 16 x Fr. 1'560.-- x 134 = Fr. 3'344'640.--. Demgegenüber beurteilte die Rekurskommission INUM die neue Verordnungsbestimmung als gesetzeswidrig, weshalb sie die alte Fassung von Art. 9 GFV weiterhin als anwendbar erachtete. Gestützt darauf zählte sie die acht Kanäle von 25 kHz pro 200 kHz, der früheren Praxis des Bundesamts entsprechend, lediglich einfach - spaltete sie also nicht in "up- und downlink-Frequenzen" auf - und multiplizierte sie mit dem leicht geringeren Tarifansatz von Fr. 1'500.-- sowie ebenfalls mit der Anzahl von 134 Kanälen landesweit. Das Resultat ergab dabei 8 x Fr. 1'500.-- x 134 = Fr. 1'608'000.--.
3. 3.1 Beim Funkfrequenzspektrum handelt es sich um ein beschränktes natürliches Gut, das dem Staat zusteht (<ref-ruling> E. 5b S. 312; BBl 1996 III 1431). Die Funkkonzessionsgebühr ist eine öffentliche Kausalabgabe mit dem Charakter eines Entgelts für die mit der Verleihung verbundene Sondernutzung des Funkfrequenzspektrums für Mobilfunkdienste (vgl. Adrian Hungerbühler, Grundsätze des Kausalabgabenrechts, in ZBl 104/2003, S. 509). Da mit der Gebühr die Nutzung eines staatlichen Regals abgegolten wird und sich ihre Höhe daher nicht anhand staatlicher Aufwendungen sondern höchstens am zu entgeltenden Nutzen - sofern ein solcher beziffert werden kann - berechnet, zählt sie zu den fiskalischen Monopolgebühren und damit zu den so genannten kostenunabhängigen Kausalabgaben (vgl. Hungerbühler, a.a.O., S. 512). Das trifft umso mehr zu, als für den geleisteten Verwaltungsaufwand gestützt auf eine besondere Gesetzesbestimmung (vgl. <ref-law>) jährlich eine separate Verwaltungsgebühr erhoben wird, welche im vorliegenden Fall im Übrigen nicht strittig ist. Die fragliche Konzessionsgebühr verfügt damit ausschliesslich über einen kostenunabhängigen Charakter.
3.2 Aus dem verfassungsrechtlichen Legalitätsprinzip folgt, dass Gebühren in rechtssatzmässiger Form festgelegt sein müssen, so dass den rechtsanwendenden Behörden kein übermässiger Spielraum verbleibt und die möglichen Abgabepflichten voraussehbar und rechtsgleich sind (vgl. Art. 164 Abs. 1 lit. d und Art. 127 Abs. 1 BV; <ref-ruling> E. 5a S. 117; Urteile des Bundesgerichts 2A.191/2005 vom 2. September 2005, E. 4.1, und 1P.645/2004 vom 1. Juni 2005, E. 3.5, mit Hinweisen; Hungerbühler, a.a.O., S. 519). Delegiert das Gesetz die Kompetenz zur rechtssatzmässigen Festlegung einer Abgabe an den Verordnungsgeber, so muss es zumindest den Kreis der Abgabepflichtigen, den Gegenstand und die Bemessungsgrundlagen selbst festlegen (<ref-ruling> E. 9a S. 179). Nach dem Kostendeckungsprinzip sollen die Gesamteingänge den Gesamtaufwand für den betreffenden Verwaltungszweig nicht oder nur geringfügig überschreiten (<ref-ruling> E. 3a/aa mit Hinweisen; Urteil des Bundesgerichts 2A.191/2005 vom 2. September 2005, E. 4.1). Das Äquivalenzprinzip verlangt in Konkretisierung des Verhältnismässigkeitsgrundsatzes insbesondere, dass eine Gebühr nicht in einem offensichtlichen Missverhältnis zum objektiven Wert der bezogenen Leistung stehen darf und sich in vernünftigen Grenzen bewegen muss (<ref-ruling> E. 4a S. 52; Urteile des Bundesgerichts 2A.191/2005 vom 2. September 2005, E. 4.1, und 1P.645/2004 vom 1. Juni 2005, E. 3.4, mit Hinweisen). Eine kostenunabhängige Kausalabgabe, wie sie hier zu beurteilen ist, untersteht freilich mangels zu entgeltendem staatlichem Aufwand nicht dem Kostendeckungsprinzip. Die Höhe der Abgabe muss daher in hinreichend bestimmter Weise bereits aus dem formellen Gesetz hervorgehen und unterliegt im Übrigen einzig dem Äquivalenzprinzip (vgl. Hungerbühler, a.a.O., S. 512 und 518).
4. 4.1 Auf Verwaltungsgerichtsbeschwerde hin kann das Bundesgericht Verordnungen des Bundesrats vorfrageweise auf ihre Gesetz- und Verfassungsmässigkeit prüfen. Bei unselbständigen Verordnungen, die sich auf eine gesetzliche Delegation stützen, prüft es, ob sich der Bundesrat an die Grenzen der ihm im Gesetz eingeräumten Befugnisse gehalten hat. Soweit das Gesetz den Bundesrat nicht ermächtigt, von der Verfassung abzuweichen, befindet das Gericht auch über die Verfassungsmässigkeit der unselbständigen Verordnung. Wird dem Bundesrat durch die gesetzliche Delegation ein sehr weiter Ermessensspielraum für die Regelung auf Verordnungsebene eingeräumt, so ist dieser Spielraum nach <ref-law> für das Bundesgericht verbindlich; es darf in diesem Falle bei der Überprüfung der Verordnung nicht sein eigenes Ermessen an die Stelle desjenigen des Bundesrats setzen, sondern es beschränkt sich auf die Prüfung, ob die Verordnung den Rahmen der dem Bundesrat im Gesetz delegierten Kompetenzen offensichtlich sprengt oder aus anderen Gründen gesetz- oder verfassungswidrig ist (<ref-ruling> E. 6.1 S. 25 f., mit Hinweisen).
4.2 Strittig ist im vorliegenden Fall einzig die Höhe der angefochtenen Konzessionsgebühr. <ref-law> sieht dazu weder einen Gebührenrahmen noch einen Maximalbetrag vor. Die Bestimmung nennt lediglich die Kriterien für die Bemessung der Gebühr. <ref-law> erteilt dem Bundesrat die Kompetenz zur Festlegung der Konzessionsgebühren sowie zur Regelung der Gebührenerhebung. Diese Kompetenz hat der Bundesrat mit Erlass der Verordnung über Gebühren im Fernmeldebereich (GFV) wahrgenommen. Wie bereits dargelegt (vgl. E. 2.3), beträgt danach die Konzessionsgebühr für Mobilfunkdienste pro zugeteilte Hochfrequenzbandbreite bis zu 25 kHz seit dem 1. Januar 2004 jährlich Fr. 1'560.-- für einen landesweit konzessionierten Dienst (Art. 9 Abs. 1 GFV in der Fassung vom 5. Dezember 2003; AS 2003 4777). Vorher errechnete sich die Konzessionsgebühr pro zugeteilten Funksprechkanal bzw. Funkfrequenzkanal bis zu 25 kHz und betrug jährlich Fr. 1'500.-- für einen landesweit konzessionierten Dienst (Art. 9 Abs. 1 aGFV; AS 1997 2897). Die Neuformulierung der Verordnungsbestimmung ist nicht rein begrifflicher Art, sondern brachte einen eigentlichen Systemwechsel mit sich. Während die Gebühr unter der alten Fassung für den ganzen Funksprechkanal erhoben wurde, geschieht dies neu für jede Hochfrequenzbandbreite separat. Die GSM-Technologie nutzt pro Funksprechkanal zwei Hochfrequenzbandbreiten, indem für eine zweiseitige Gesprächsverbindung am Mobiltelefon zwei Senderichtungen benötigt werden, nämlich die zur Antennenanlage hinführende (so genannter "uplink") sowie die davon wegführende (so genannter "downlink"). Die neue Fassung von Art. 9 Abs. 1 GFV führte daher im Vergleich zum alten Wortlaut zu einer Verdoppelung der Gebühr. Da gleichzeitig der Grundbetrag um Fr. 60.-- erhöht wurde, stieg die Konzessionsgebühr 2004 im Vergleich zum Vorjahr insgesamt um 108 % an.
4.3 Mit der Anpassung der Konzessionsgebühren bezweckte der Bundesrat, wie sich insbesondere aus der Vernehmlassungseinladung des Bundesamtes vom 17. Juni 2003 an die interessierten Kreise ergibt, eine stärkere Partizipation des Staates am wirtschaftlichen Erfolg der Konzessionärinnen von Mobilfunknetzen. Danach rechtfertigt der gestiegene Marktwert eine höhere Gebühr. Eine solche Herleitung erscheint angesichts der grundsätzlichen Ausrichtung der Konzessionsgebühr am Wert des verliehenen Nutzungsrechts nicht von vornherein unzulässig, sofern sie das Äquivalenzprinzip einhält. Fraglich ist vorliegend jedoch, ob dieses auf Verordnungsstufe eingeführte ökonomische Kriterium durch <ref-law> gedeckt wird. Darin werden als Bemessungskriterien indes lediglich der zugeteilte Frequenzbereich und die Frequenzklasse, die zugeteilte Bandbreite, die räumliche Ausdehnung sowie die zeitliche Nutzung genannt. Ein wirtschaftliches Kriterium sieht <ref-law> nicht vor. Der Wert des verliehenen Rechts bestimmt sich einzig anhand der gesetzlichen Kriterien (vgl. BBl 1996 III 1440) und damit ohne Berücksichtigung der Gewinnchancen der Konzessionäre. Der Bundesrat war sich dessen übrigens bewusst, hat er doch dem Gesetzgeber im Rahmen der Revision des Fernmeldegesetzes unter anderem eine Ergänzung von <ref-law> um das wirtschaftliche Kriterium des "Werts der Frequenzen" vorgeschlagen (vgl. die Botschaft des Bundesrates vom 12. November 2003 zur Änderung des Fernmeldegesetzes, in BBl 2003 7951, insbes. S. 7985 und 8018). Danach soll dieses Kriterium künftig erlauben, die Höhe der Gebühren entsprechend der Nachfrage der Frequenzen festzulegen (BBl 2003 7985). Die entsprechende Gesetzesnovelle liegt zurzeit noch immer beim Parlament. Nachdem dieses Kriterium somit bisher im Gesetz noch nicht enthalten ist und der Bundesrat selbst vorschlägt, die entsprechende Lücke zu schliessen, lässt sich eine Verordnungsregelung, die gerade den wirtschaftlichen Wert der Frequenzen als Bemessungsgrundlage für die Gebührenberechnung beizieht, derzeit nicht auf das Gesetz abstützen. Dieses Manko wird auch nicht durch das Äquivalenzprinzip behoben, das im vorliegenden Zusammenhang, wie allgemein bei fiskalischen Regal- und Monopolgebühren (vgl. Hungerbühler, a.a.O., S. 526), kaum Richtlinien für eine Begrenzung des Gebührenbetrags zu vermitteln vermag. Daran ändert auch ein Vergleich mit den Konzessionsgebühren anderer Staaten nichts, die möglicherweise ohnehin einzig auf (den hier ausgeschlossenen) wirtschaftlichen Kriterien beruhen.
4.4 Die neue Verordnungsbestimmung beruht demnach nicht auf einer genügenden gesetzlichen Grundlage, womit sie nicht zur Anwendung gelangen kann, wie der angefochtene Entscheid zu Recht festhält. Da es dem bundesrätlichem Verordnungsrecht an einer rechtsgenüglichen Gesetzesdelegation mangelt und es nicht um eine im Gesetz angelegte Verfassungswidrigkeit geht, liegt kein Anwendungsfall von <ref-law> vor, weshalb das Bundesgericht und damit auch die Vorinstanz nicht dem verfassungsrechtlichen Anwendungsgebot verfassungswidrigen Gesetzesrechts unterliegen (vgl. dazu auch <ref-ruling>).
5. Die Anwendung der neuen Bestimmung von Art. 9 Abs. 1 GFV erweist sich demnach schon deshalb als unzulässig, weil diese nicht auf einer genügenden gesetzlichen Grundlage beruht. Damit braucht nicht mehr geprüft zu werden, ob es sich bei der fraglichen Konzessionsgebühr um ein wohlerworbenes Recht handelt, was die Anwendbarkeit der revidierten Verordnung während der laufenden Konzessionsdauer ausschlösse. Dazu kann immerhin darauf hingewiesen werden, dass die Konzessionsgebühr gerade nicht in der Konzessionsurkunde bestimmt wird, sondern jährlich neu festgelegt wird, und die Urkunde darüber hinaus Änderungen des Gesetzes- und Verordnungsrechts ausdrücklich vorbehält (vgl. dazu das Urteil des Bundesgerichts 2P.13/2005 vom 21. Juni 2005, E. 3). Im Übrigen ist es unter diesen Umständen nicht zu beanstanden, dass die Rekurskommission INUM mangels Alternativen die Konzessionsgebühr für das Jahr 2004 nach den Kriterien des alten Verordnungsrechts festsetzte.
6. Die Verwaltungsgerichtsbeschwerde erweist sich als unbegründet und ist abzuweisen.
Da das unterliegende beschwerdeführende Departement im vorliegenden Fall Vermögensinteressen des Bundes verfolgt, wird es für das bundesgerichtliche Verfahren kostenpflichtig (Art. 156 Abs. 2, Art. 153 und 153a OG). Eine Parteientschädigung ist nicht geschuldet, nachdem die obsiegende Beschwerdegegnerin nicht durch einen unabhängigen Rechtsanwalt, sondern durch zwei eigene Mitarbeiter vertreten ist (vgl. dazu das Urteil 2A.191/2005 vom 2. September 2005, E. 6).

Demnach erkennt das Bundesgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 20'000.-- wird dem Eidgenössischen Departement für Umwelt, Verkehr, Energie und Kommunikation auferlegt.
3. Dieses Urteil wird den Parteien und der Eidgenössischen Rekurskommission für Infrastruktur und Umwelt schriftlich mitgeteilt.
Lausanne, 17. Oktober 2005
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: