Sachverhalt:
A. X._, der sich als staatenlos bezeichnet, reiste im Winter 2008/09 unter Verwendung eines bulgarischen Reisepasses über Griechenland in die Schweiz ein und stellte hier ein Asylgesuch. Das Bundesamt für Migration (im Folgenden: BFM) trat darauf mit Entscheid vom 24. August 2009 nicht ein und wies X._ nach Griechenland weg. Zudem verhängte es gegen ihn für den Zeitraum vom 9. Oktober 2009 bis zum 8. Oktober 2010 eine Einreisesperre. X._ vereitelte seine Überstellung nach Griechenland zwei Mal durch renitentes Verhalten, weshalb er schliesslich am 16. Dezember 2009 mit einem Sonderflug ausgeschafft werden musste.
Nach kurzer Inhaftierung will X._ Griechenland verlassen und sich einige Monate in der Türkei aufgehalten haben. In der Folge gelangte er auf dem Landweg wieder in die Schweiz und traf am 26. April 2010 in Zürich ein, wo er am folgenden Tag erneut ein Asylgesuch stellte. Er wurde dem Kanton Graubünden zugewiesen (Verfügung des BFM vom 17. Juni 2010) und hatte sich am Folgetag im Erst- und Aufnahmezentrum A._ in Chur einzufinden. Von dort entfernte er sich alsbald ohne Erlaubnis.
Nachdem das BFM die griechischen Behörden nach den Vorschriften der sog. Dublin-Verordnung um Übernahme von X._ ersucht hatte, trat es mit Verfügung vom 21. Juni 2010 gestützt auf Art. 34 Abs. 2 lit. d des Asylgesetzes vom 26. Juni 1998 (AsylG; SR 142.31) auf das Asylgesuch nicht ein und wies ihn aus der Schweiz nach Griechenland weg.
B. Am 23. Juni 2010 wurde X._ auf Anordnung des Amtes für Polizeiwesen und Zivilrecht Graubünden in Ausschaffungshaft genommen. Gleichentags liess X._ Beschwerde gegen den Asylentscheid beim Bundesverwaltungsgericht erheben und verfügte dieses die sofortige Aussetzung des Wegweisungsvollzugs bis zum Entscheid über die beantragte aufschiebende Wirkung. Am 25. Juni 2010 wurde X._ dem Bezirkspräsidium Plessur vorgeführt. Das Bezirkspräsidium bestätigte die Ausschaffungshaft bis zum 22. September 2010, wobei es X._, der sich nun als Kurde aus Syrien bezeichnete, die unentgeltliche Rechtspflege gewährte.
Ebenfalls am 25. Juni 2010 hiess das Bundesverwaltungsgericht das Gesuch von X._ gut, seiner Beschwerde gegen den Asylentscheid die aufschiebende Wirkung beizulegen. Es führte aus, von verschiedener Seite, insbesondere auch vom UNHCR, würden der ordnungsgemässe Zugang zum Asylverfahren in Griechenland und die dortigen Aufnahmebedingungen in Frage gestellt. Das Bundesverwaltungsgericht sei mit einer eingehenderen Prüfung der Aspekte und Kriterien für eine Überstellung von Asylsuchenden in dieses Land befasst. Da begründete Anhaltspunkte für eine Verletzung der EMRK durch Griechenland bestünden, werde der beantragte Vollzugsaufschub gewährt.
C. Gegen die Bestätigung der Ausschaffungshaft beschwerte sich X._ erfolglos beim Kantonsgericht Graubünden. Dessen II. Strafkammer führte in ihrem Entscheid vom 6. Juli 2010 aus, es seien gleich mehrere Haftgründe gegeben und die Wegweisung sei angeordnet und eröffnet worden. Da die Nichteintretensverfügung des BFM nicht gerade willkürlich oder gar nichtig erscheine, sei sie für das Haftgericht grundsätzlich verbindlich. Die Gewährung der aufschiebenden Wirkung durch die Beschwerdeinstanz (das Bundesverwaltungsgericht) ändere daran nichts. Die Haft sei deshalb nur aufzuheben, wenn die Ausschaffung aus triftigen Gründen als undurchführbar erscheine oder praktisch feststehe, dass sie sich innert vernünftiger Frist nicht realisieren lasse. Falls noch eine gewisse Vollzugsaussicht bestehe, erscheine die Haftanordnung nicht als unverhältnismässig und damit unzulässig. Das Ergebnis der Überprüfung durch das Bundesverwaltungsgericht sei offen. Da davon ausgegangen werden könne, dass dieses die Sache mit der erforderlichen Dringlichkeit behandeln werde und deshalb jedenfalls eine erhebliche Ausdehnung der Haft nicht gewärtigt werden müsse, erscheine die Haftanordnung - auch mit Blick auf die mögliche Gesamtlänge dieser Massnahme - nicht als unverhältnismässig.
D. Mit Eingabe vom 12. Juli 2010 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Er beantragt, das Erkenntnis des Kantonsgerichts in der Sache aufzuheben und ihn aus der Ausschaffungshaft zu entlassen. Die griechischen Behörden hätten sein Asylgesuch nicht behandeln wollen, und er habe sich in der Folge mehr als drei Monate ausserhalb des sog. Schengenraumes aufgehalten, weshalb die Verpflichtung von Griechenland erloschen und die Schweiz zur Gesuchbehandlung zuständig sei. Zudem erscheine eine Gutheissung der Beschwerde durch das Bundesverwaltungsgericht als "überwiegend wahrscheinlich" und habe das BFM eine vertiefte Prüfung der Zumutbarkeit des Wegweisungsvollzugs unterlassen. Mit einem Vollzug innert der gesetzlich vorgesehenen Haftdauer könne nicht gerechnet werden, weshalb die Haft unverhältnismässig sei.
Der Beschwerdeführer ersucht im Weiteren um Gewährung der unentgeltlichen Rechtspflege unter Beiordnung des beigezogenen Rechtsanwalts.
E. Das Amt für Polizeiwesen und Zivilrecht Graubünden beantragt, die Beschwerde abzuweisen. Das Bezirksgericht Plessur hat auf eine Vernehmlassung verzichtet. Das Kantonsgericht Graubünden schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das BFM hat sich nicht vernehmen lassen.
Der Beschwerdeführer hat mit Schreiben vom 20. Juli 2010 auf abschliessende Bemerkungen verzichtet.

Erwägungen:
1. 1.1 Die zuständige Behörde kann einen Ausländer in Ausschaffungshaft nehmen oder in dieser belassen, wenn die Voraussetzungen von Art. 76 Abs. 1 des Bundesgesetzes über die Ausländerinnen und Ausländer vom 16. Dezember 2005 (AuG; SR 142.20) erfüllt sind. Danach ist erforderlich, dass ein erstinstanzlicher, nicht notwendigerweise auch rechtskräftiger Weg- oder Ausweisungsentscheid vorliegt, dessen Vollzug noch nicht möglich, aber absehbar ist. Zudem muss einer der in Art. 76 Abs. 1 lit. b AuG genannten Haftgründe bestehen, der Vollzug der Wegweisung mit dem nötigen Nachdruck verfolgt werden (Art. 76 Abs. 4 AuG; Beschleunigungsgebot) und die Haft als Ganzes verhältnismässig sein (vgl. <ref-ruling> E. 1 S. 58, mit zahlreichen Hinweisen).
1.2 Gemäss Art. 80 Abs. 6 lit. a AuG ist die Haft zu beenden, wenn der Haftgrund entfällt oder sich erweist, dass der Vollzug der Weg- oder Ausweisung aus rechtlichen oder tatsächlichen Gründen undurchführbar ist. Diesfalls lässt sie sich nicht mehr mit einem hängigen Ausweisungsverfahren rechtfertigen und verstösst sie gegen Art. 5 Ziff. 1 lit. f EMRK (<ref-ruling> E. 3 S. 152 f.; <ref-ruling> E. 4.1.1 S. 60 mit Hinweisen). Wie es sich mit der Durchführbarkeit 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 erscheint oder nicht. Die Haft hat, weil unverhältnismässig, dann als unzulässig zu gelten, wenn triftige Gründe dafür sprechen, dass die Wegweisung innert vernünftiger Frist nicht wird vollzogen werden können (<ref-ruling> E. 4.1.3 S. 61 mit Hinweisen). Blosse Erschwernisse, die eine gewisse Zeit in Anspruch nehmen, machen die Ausschaffung aber nicht bereits undurchführbar. Gerade wegen solcher Schwierigkeiten hat der Gesetzgeber die Möglichkeit der Haftverlängerung und eine relativ lange höchstzulässige Haftdauer von 18 Monaten vorgesehen (Art. 76 Abs. 3 AuG).
2. Die Vorinstanz hat zutreffend dargelegt, dass der beim Bundesverwaltungsgericht angefochtene Nichteintretens- und Wegweisungsentscheid des BFM eine Anordnung im Sinne von Art. 76 Abs. 1 AuG darstellt und dass die Haftgründe von Art. 76 Abs. 1 lit. b Ziff. 1 i.V.m. Art. 75 Abs. 1 lit. c AuG (Missachtung eines Einreiseverbots) und von Art. 76 Abs. 1 lit. b Ziff. 4 AuG (Missachtung behördlicher Anordnungen) gegeben sind. Was der Beschwerdeführer dagegen vorbringt, dringt nicht durch. Es ist nicht einzusehen, weshalb die gegen ihn verhängte und ihm bekannte Einreisesperre hätte unverbindlich sein sollen, nur weil er den Schengenraum für einige Zeit verlassen haben will. Die Vorinstanz hat in diesem Zusammenhang auch richtig darauf hingewiesen, dass er - auf dem Landweg anreisend - schon in einem anderen sicheren Land ein Asylgesuch hätte stellen können, bevor er die Schweiz erreichte. Im Weiteren hat der Beschwerdeführer verschiedentlich und zur Genüge aufgezeigt, dass er sich an behördliche Anordnungen, die ihm missfallen, nicht gebunden fühlt. Die Kritik des Beschwerdeführers geht in dieser Hinsicht offenkundig fehl.
3. Weniger klar erscheint die Durchführbarkeit der Wegweisung nach Griechenland innert vernünftiger Frist, nachdem das Bundesverwaltungsgericht der bei ihm hängigen Beschwerde die aufschiebende Wirkung gestützt auf <ref-law> (d.h. wegen begründeten Anhaltspunkten für eine Verletzung der EMRK-Garantien im Bestimmungsland) zuerkannt hat. Das Bundesverwaltungsgericht hat zu erkennen gegeben, dass es ausgehend von mehreren hängigen Fällen verschiedene Aspekte betreffend das Asylwesen in Griechenland detaillierter überprüfen will und ein Entscheid, der sich auch auf die Rechtsstellung des Beschwerdeführers auswirken könnte, nicht vor dem Herbst 2010 ergehen wird. Die Vorinstanz hat dies bei ihrer Prognose über die Durchführbarkeit einbezogen und befunden, diese Unwägbarkeiten und Verzögerungen liessen den Vollzug der Wegweisung noch nicht als in absehbarer Zeit undurchführbar erscheinen. Der Ausgang des Verfahrens vor dem Bundesverwaltungsgericht sei offen, und es könne davon ausgegangen werden, dass sich dieses der Tragweite und Dringlichkeit des zu fällenden Entscheids bewusst sei und dem Beschleunigungsgebot gemäss <ref-law> die nötige Beachtung schenke, so dass die verfügte Ausschaffungshaft voraussichtlich nicht in erheblichem Ausmass verlängert werden müsse. Zu berücksichtigen sei auch, dass es sich um eine erstmalige Haftanordnung handle und nicht um eine wiederholte Verlängerung, und dass das Verhalten des Beschwerdeführers erschwerend ins Gewicht falle. Soweit erforderlich könne die Situation im Rahmen von Haftverlängerungsentscheiden oder Haftentlassungsgesuchen neu beurteilt werden.
Was der Beschwerdeführer dagegen einwendet, lässt den angefochtenen Entscheid nicht als unrechtmässig erscheinen. Der Umstand allein, dass das Bundesverwaltungsgericht einem bei ihm eingereichten Rechtsmittel betreffend das Asyl und die Wegweisung die aufschiebende Wirkung zuerkannt hat, erlaubt noch nicht den Schluss auf Undurchführbarkeit des Vollzugs (vgl. Urteil 2C_804/2008 vom 5. Dezember 2008 E. 4.3 mit Hinweis). Dies wäre erst der Fall, wenn mit hoher Wahrscheinlichkeit mit einem gutheissenden Entscheid oder mit einer langen Verfahrensdauer zu rechnen wäre (vgl. Urteil 2A.304/2005 vom 26. Mai 2005 E. 2.1). Entgegen der Auffassung des Beschwerdeführers ist eine genauere Prognose über die Auswirkungen des vom Bundesverwaltungsgericht in Aussicht gestellten Entscheids auf den Beschwerdeführer aber schwierig und mit erheblichen Unsicherheiten behaftet. Auch wenn sich offenbar ernstzunehmende Fragen rund um die Gewährleistung der Garantien der EMRK in Griechenland stellen, kann doch nicht ohne Weiteres davon ausgegangen werden, das Bundesverwaltungsgericht gelange zum Ergebnis, dass ein in den europäischen Institutionen und der Europäischen Union fest verankertes Land die Garantien der EMRK und seine einschlägigen internationalen Verpflichtungen generell und systematisch missachte in einem Ausmass, dass die Regeln der Dublin-Verordnung über die Behandlung von Asylgesuchen im Verkehr mit diesem Land weitgehend ausser Kraft gesetzt werden müssten und der Wegweisungsvollzug undurchführbar sei. Die zu erwartende Verfahrensdauer erscheint aus heutiger Sicht auch nicht als übermässig lang oder gar unbestimmt. Auch wenn der in Aussicht gestellte Entscheid mit einiger Wahrscheinlichkeit nicht mehr während der bestätigten Haftdauer von drei Monaten ergehen dürfte und eine Verlängerung der Haft in Betracht zu ziehen ist, durfte die Vorinstanz ohne Bundesrecht zu verletzen davon ausgehen, eine allfällige Verlängerung werde ein vertretbares Mass nicht überschreiten. Mit Blick auf die weiteren Umstände, insbesondere dass es sich um die erstmalige Anordnung von Ausschaffungshaft handelt und der Beschwerdeführer eine hartnäckige Renitenz und ausgeprägte Geringschätzung behördlicher Anordnungen an den Tag gelegt hat (vier Monate nach der Überstellung mittels Sonderflug war er trotz Einreisesperre wieder in der Schweiz, ohne dass ein Zwang zu solchem Verhalten erkennbar ist), kann die Bestätigung der Haftanordnung nicht als unverhältnismässig bezeichnet werden. Die Beschwerde ist daher abzuweisen.
4. Bei diesem Ergebnis wird der Beschwerdeführer an sich kostenpflichtig (<ref-law>). Da die Beschwerde aber nicht gerade als von vornherein aussichtslos zu bezeichnen ist und die Bedürftigkeit des Beschwerdeführers als erstellt gelten kann, ist dem Gesuch um Gewährung der unentgeltlichen Rechtspflege unter Beiordnung des beigezogenen Rechtsanwalts zu entsprechen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Dem Beschwerdeführer wird für das Verfahren vor Bundesgericht die unentgeltliche Rechtspflege gewährt.
a) Es werden keine Gerichtskosten erhoben.
b) Rechtsanwalt Bernhard Jüsi, Zürich, wird zum unentgeltlichen Rechtsbeistand bestellt und aus der Bundesgerichtskasse mit Fr. 2'000.-- entschädigt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Amt für Polizeiwesen und Zivilrecht Graubünden, dem Bezirksgerichtspräsidium Plessur, dem Kantonsgericht von Graubünden, II. Strafkammer, dem Bundesamt für Migration und dem Bundesverwaltungsgericht (zur Orientierung, ad D-4529/2010) schriftlich mitgeteilt.
Lausanne, 6. August 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Merkli Winiger