Sachverhalt:
A. X._, geb. 1986, stammt aus der Demokratischen Republik Kongo. Er reiste nach eigenen Angaben am 17. Februar 2004 illegal in die Schweiz ein und stellte hier ein Asylgesuch. Dieses wurde mit Urteil der Schweizerischen Asylrekurskommission vom 28. April 2005 rechtskräftig abgewiesen. X._ erhielt eine Frist zur Ausreise aus der Schweiz bis zum 29. Juni 2005. Er blieb aber hier, teilte den Migrationsbehörden wiederholt mit, nicht in seine Heimat zurückzukehren, und weigerte sich, an Ausreisevorbereitungen mitzuwirken oder ein Ausweispapier vorzulegen. Am 20. Februar 2007 belegte ihn das Amt für Polizeiwesen und Zivilrecht Graubünden mit einer Eingrenzung. Vom 23. April 2007 an galt er als verschwunden. Vom 23. Juni bis zum 19. Oktober 2007 befand er sich im Kanton Zürich wegen Verstosses gegen ausländerrechtliche Bestimmungen im Strafvollzug. Den Behörden gegenüber äusserte er neu die Absicht, in der Schweiz heiraten zu wollen, wozu er nunmehr einen kongolesischen Pass vorzulegen vermochte. Mit Verfügung vom 20. Oktober 2007 ordnete das Amt für Polizeiwesen und Zivilrecht Graubünden die Ausschaffungshaft bis zum 19. Januar 2008 an. Ein Ausschaffungsversuch scheiterte am 22. Oktober 2007, da sich X._ weigerte, das Flugzeug zu besteigen. Mit Urteil vom 23. Oktober 2007 prüfte und bestätigte das Bezirksgerichtspräsidium Plessur die angeordnete Ausschaffungshaft.
B. Am 18. Januar 2008 verlängerte das Bezirksgerichtspräsidium Plessur die Haft bis zum 2. März 2008. Am 4. Februar 2008 scheiterte ein weiterer Ausschaffungsversuch daran, dass die zuständige kongolesische Zivilluftfahrtbehörde einem entsprechenden Sonderflug die Landebewilligung verweigerte. Mit Entscheid vom 28. Februar 2008 wies das Bezirksgerichtspräsidium Plessur ein erneutes Gesuch um Fortsetzung der Ausschaffungshaft ab und ordnete an, X._ sei unverzüglich aus der Haft zu entlassen.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 27. März 2008 an das Bundesgericht beantragt das Bundesamt für Migration, den Entscheid des Bezirksgerichtspräsidiums Plessur vom 28. Februar 2008 aufzuheben.
Das Amt für Polizeiwesen und Zivilrecht Graubünden schliesst auf Gutheissung der Beschwerde. Das Bezirksgericht Plessur hat auf eine Vernehmlassung verzichtet. X._ hat innert Frist zur Beschwerde nicht Stellung genommen.
D. Nach seiner Haftentlassung ist X._ verschwunden; jedenfalls wissen die Behörden nicht, wo er sich zurzeit aufhält.

Erwägungen:
1. 1.1 Nach Art. 89 Abs. 2 lit. a BGG in Verbindung mit Art. 14 Abs. 2 der Organisationsverordnung vom 17. November 1999 für das Eidgenössische Justiz- und Polizeidepartement (OV-EJPD; SR 172.213.1) ist das Bundesamt für Migration in den Bereichen des Ausländer- und Bürgerrechts ermächtigt, beim Bundesgericht Beschwerde gegen letztinstanzliche kantonale Entscheide zu führen. Die Legitimation des Bundesamtes zur Beschwerde hat zum Zweck, die richtige und einheitliche Anwendung des Bundesrechts zu sichern. Es hat daher nicht darzulegen, dass es ein spezifisches schutzwürdiges (öffentliches) Interesse im Sinne von Art. 89 Abs. 1 lit. c BGG an der Aufhebung des angefochtenen Entscheids hat. Erforderlich ist nur, dass es ihm nicht um die Behandlung abstrakter Fragen des objektiven Rechts, sondern um konkrete Rechtsfragen eines tatsächlich bestehenden Einzelfalles geht (vgl. <ref-ruling> E. 1.1 S. 4; <ref-ruling> E. 1 S. 195 f., je mit Hinweisen).
1.2 Im vorliegenden Fall ist die Absehbarkeit des Vollzugs der ausgesprochenen Wegweisung fraglich. Das Bundesamt verfolgt mit seiner Beschwerde die Klärung dieser Rechtsfrage im konkreten Fall des Beschwerdegegners. Diese Klärung soll unter anderem dazu dienen, dass die Bemühungen der beteiligten Behörden und insbesondere des Bundesamts selbst im Rahmen der Vollzugshilfe nicht ins Leere laufen, indem wie hier ausländische Personen aus der Haft entlassen werden und dann verschwinden. Die Beschwerde zeitigt insofern im Hinblick auf allfällige künftige, ähnlich gelagerte Fälle auch Wirkung über den Einzelfall hinaus.
2. 2.1 Strittig ist die Fortsetzung einer Ausschaffungshaft gemäss Art. 76 AuG. Nach Art. 80 Abs. 6 lit. a AuG wird die Haft unter anderem dann beendet, wenn sich erweist, dass der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar ist.
2.2 Wie es sich mit der Durchführbarkeit des Wegweisungsvollzugs im Einzelnen verhält, bildet Gegenstand einer nach pflichtgemässem Ermessen vorzunehmenden Prognose. Massgebend ist, ob die Ausschaffung mit hinreichender Wahrscheinlichkeit innert absehbarer Zeit möglich sein wird oder nicht. Die Haft ist dann unverhältnismässig und damit auch unzulässig, wenn triftige Gründe für die Undurchführbarkeit des Vollzugs sprechen oder praktisch feststeht, dass er sich innert vernünftiger Frist kaum wird realisieren lassen. Dies ist in der Regel bloss der Fall, wenn die Ausschaffung auch bei gesicherter Kenntnis der Identität oder der Nationalität des Betroffenen bzw. trotz seines Mitwirkens bei der Papierbeschaffung mit grosser Wahrscheinlichkeit als ausgeschlossen erscheint. Zu denken ist etwa an eine länger dauernde Transportunfähigkeit aus gesundheitlichen Gründen oder an eine ausdrückliche oder zumindest klar erkennbare und konsequent gehandhabte Weigerung eines Staates, gewisse Staatsangehörige zurückzunehmen. Nur falls keine oder bloss eine höchst unwahrscheinliche, rein theoretische Möglichkeit besteht, die Wegweisung zu vollziehen, ist die Haft aufzuheben, nicht indessen bei einer ernsthaften, wenn auch allenfalls (noch) geringen Aussicht hierauf. Eine Beeinträchtigung der öffentlichen Ordnung durch den Betroffenen vorbehalten, welche die Verhältnismässigkeit der Aufrechterhaltung der Haft wegen eines überwiegenden öffentlichen Interesses in einem anderen Licht erscheinen lassen kann, ist dabei nicht notwendigerweise auf die maximale Haftdauer, sondern vielmehr auf einen den gesamten Umständen des konkreten Falles angemessenen Zeitraum abzustellen (vgl. <ref-ruling> E. 4.1.3 S. 61, 127 II 168 E. 2c S. 172; <ref-ruling> E. 2; <ref-ruling> E. 3 S. 152 f.). Namentlich macht der Umstand allein, dass die Ausreise nur schwer organisiert werden kann und im Rahmen der entsprechenden Bemühungen mit ausländischen Behörden erst noch verhandelt werden muss, was erfahrungsgemäss eine gewisse Zeit in Anspruch nimmt, die Ausschaffung nicht bereits undurchführbar (vgl. BGE <ref-ruling> E. 2 S. 220).
2.3 Im vorliegenden Fall besteht weder ein rechtliches Hindernis des Wegweisungsvollzugs noch weigert sich der Heimatstaat des Beschwerdegegners grundsätzlich, diesen zurückzunehmen. Die Ausschaffung des Beschwerdegegners scheiterte lange Zeit daran, dass dieser bei der Organisation der Ausreise nicht mitwirkte und die Existenz seiner Ausweispapiere verheimlichte. Erst nachdem er diese im Zusammenhang mit der geplanten Heirat vorlegte, konnte eine Ausreise vorbereitet werden. Zusammen mit den zuständigen Behörden der Demokratischen Republik Kongo wurde die Möglichkeit der zwangsweisen Rückführung von Staatsangehörigen dieses Landes ausgehandelt. Sowohl das Innen- als auch das Aussenministerium erteilten in der Folge die Bewilligung für die Durchführung eines Sonderfluges am 4./5. Februar 2008, mit dem auch der Beschwerdegegner ausgeschafft werden sollte. Am 4. Februar 2008 weigerte sich die für Zivilluftfahrt zuständige kongolesische Behörde, offenbar aufgrund innerkongolesischer Uneinigkeiten, ohne weitere Begründung, die Landebewilligung zu erteilen, wodurch die Ausschaffung des Beschwerdegegners scheiterte. Am 14. Februar 2008 teilte das Bundesamt der kantonalen Migrationsbehörde mit, dass sich nicht bestimmen lasse, wann die nächste Ausschaffung in die Demokratische Republik Kongo organisiert werden könne; ein neuer Sonderflug fände mit Sicherheit nicht vor einem Monat statt und liesse sich diesfalls wohl nur in Verbindung mit einer anderen Zieldestination durchführen.
2.4 Zurzeit kann nicht davon ausgegangen werden, dass sich der Heimatstaat des Beschwerdegegners klar erkennbar und konsequent generell weigert, seine Staatsangehörigen zurückzunehmen. Zwar scheinen zwischen den kongolesischen Behörden Widersprüche zu bestehen, die bereinigt werden müssen, worauf die Schweiz wenig bis keinen Einfluss hat. Dennoch haben sich verschiedene kongolesische Stellen zur Rücknahme von ausgeschafften Landsleuten positiv geäussert und eine solche auch in Aussicht gestellt. Damit kann nicht geschlossen werden, die Demokratische Republik Kongo sei offensichtlich nicht bereit, ihre Staatsangehörigen zurückzunehmen. Es handelt sich vielmehr um ein Problem, das unter Umständen innert absehbarer Zeit gelöst werden kann, was die Ausschaffung des Beschwerdegegners derzeit nicht als tatsächlich unmöglich erscheinen lässt. Im Übrigen hätte es dieser in der Hand, mit seinen gültigen heimatlichen Papieren jederzeit selbständig und freiwillig aus der Schweiz auszureisen und damit der seit dem 29. Juni 2005 ergangenen behördlichen Anweisung zur Ausreise aus der Schweiz Folge zu leisten und die Ausschaffungshaft zu beenden.
2.5 Schliesslich hätte der Haftrichter selbst dann, wenn seine Auffassung zutreffen würde, ergänzend prüfen müssen, ob gegebenenfalls anstelle der Ausschaffungshaft die Durchsetzungshaft nach Art. 78 AuG anzuordnen bzw. die bestehende Ausschaffungs- in Durchsetzungshaft umzuwandeln gewesen wäre. Wie es sich damit verhält, kann jedoch offen bleiben, da jedenfalls entgegen dem angefochtenen Entscheid bereits die Ausschaffungshaft zu bestätigen ist.
2.6 Der angefochtene Entscheid verstösst somit gegen Bundesrecht.
3. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten erweist sich als begründet und ist gutzuheissen. Gleichzeitig ist der angefochtene Entscheid aufzuheben.
Angesichts der Umstände des Falles rechtfertigt es sich, von der Erhebung von Kosten abzusehen (vgl. Art. 66 Abs. 1 zweiter Satz BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, und das Urteil des Bezirksgerichtspräsidiums Plessur vom 28. Februar 2008 wird aufgehoben.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Parteien und dem Bezirksgerichtspräsidium Plessur schriftlich mitgeteilt.
Lausanne, 10. Juni 2008
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Merkli Uebersax