Sachverhalt: A. Am 14. Oktober 2008 stellte die Swisscom (Schweiz) AG ein Gesuch um Errichtung einer Mobilfunk-Basisstation auf dem Dach des Gebäudes auf Parzelle Nr. 6717 an der Tittwiesenstrasse 29 in Chur. Mit Entscheid vom 11. Januar 2010 wies der Stadtrat Chur die dagegen erhobenen Einsprachen ab, soweit er darauf eintrat, und erteilte die Baubewilligung unter Auflagen und Bedingungen. Ein Teil der Einsprecher (darunter die im Rubrum aufgeführten Beschwerdeführer) erhoben gegen diesen Entscheid Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Sie machten insbesondere geltend, ihr Anspruch auf rechtliches Gehör sei verletzt worden, weil ihnen ein Schreiben vom 10. Dezember 2009 der Swisscom (Schweiz) AG an die Stadt Chur betreffend die Standortevaluation und das Mobilfunkkonzept für das Jahr 2010 vorenthalten worden sei. Mit Urteil vom 7. September 2010 wies das Verwaltungsgericht die Beschwerde ab. Es erwog, die geltend gemachte Gehörsverletzung sei im Rahmen des Schriftenwechsels vor Verwaltungsgericht geheilt worden. Die übrigen Rügen, insbesondere bezüglich angeblicher weiterer Gehörsverletzungen, hielt es für unbegründet. Eine gegen das Urteil des Verwaltungsgerichts eingereichte Beschwerde in öffentlich-rechtlichen Angelegenheiten hiess das Bundesgericht mit Urteil 1C_50/2011 vom 11. August 2011 gut. Es bejahte darin eine Verletzung des Anspruchs auf rechtliches Gehör der Beschwerdeführer in Bezug auf ein nicht in den Akten enthaltenes Protokoll einer Besprechung vom 26. August 2009 zwischen der Stadt Chur und der Swisscom. Es hob das Urteil der Verwaltungsgerichts vom 7. September 2010 auf und wies die Angelegenheit zur Gewährung des rechtlichen Gehörs und zu neuem Entscheid an das Verwaltungsgericht zurück. B. Im Rahmen der weiteren Behandlung der Streitsache stellte das Verwaltungsgericht fest, dass von der erwähnten Besprechung vom 26. August 2009 kein Protokoll existiert. Aus den von der Stadt Chur ins Recht gelegten Beilagen 14 - 21 sowie den Stellungnahmen der Swisscom und der Stadt Chur ergebe sich indessen das damalige Gesprächsthema. Das Festhalten der Beschwerdeführer an der Auffassung, eine qualifizierte Stellungnahme sei für sie unmöglich, weshalb die Verletzung des rechtlichen Gehörs nach wie vor bestehe, erweise sich vor diesem Hintergrund als unbegründet. Das Verwaltungsgericht hielt mit Urteil vom 27. Januar 2012 mangels anderweitiger neuer Erkenntnisse an seinem Entscheid vom 7. September 2010 fest und wies die Beschwerde ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 24. April 2012 beantragen die im Rubrum genannten Beschwerdeführer, das Urteil des Verwaltungsgerichts vom 27. Januar 2012 sei aufzuheben und die Angelegenheit sei zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Sie beschweren sich wiederum über eine Missachtung ihres Gehörsanspruchs. Das Verwaltungsgericht beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werde. Die Stadt Chur und die Swisscom stellen Antrag auf Abweisung der Beschwerde. In ihrer Stellungnahme dazu halten die Beschwerdeführer im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest. D. Mit Präsidialverfügung vom 30. Mai 2012 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung beigelegt.