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. 