Sachverhalt: A. Der Gemeindevorstand Ruschein leitete am 18. November 1992 ein Quartierplanverfahren für das in der Bauzone gelegene Gebiet "Sut Baselgias" ein und erliess am 19. Juli 1995 einen Quartierplan. Im Quartierplangebiet befinden sich insbesondere die Parzellen Nrn. 281 und 282. Am 24. August 1998 beschloss der Gemeindevorstand eine erste Änderung des Quartierplans. 1999 wurden auf den vom Grundstück Nr. 281 abparzellierten Parzellen Nrn. 548 und 549 zwei Einfamilienhäuser erstellt. B._ ist seit 2005 Eigentümerin der Parzelle Nr. 548; A._ erwarb 2010 die Parzelle Nr. 549. Auf den übrigen Parzellen Nr. 529 (von Nr. 282 abparzelliert), Nr. 282 (Rest), Nr. 553 (von Nr. 281 abparzelliert) und Nr. 281 (Rest) wurde seit 1998 dagegen nicht gebaut. Diese vier Grundstücke stehen im Eigentum von D._. Vermutlich anfangs 2011 ersuchte D._ gemeinsam mit der C._ AG um eine Änderung des Quartierplans, da aufgrund der Steilheit des Geländes eine rationelle Überbauung ansonsten nicht bewerkstelligt werden könne. Erforderlich seien eine Nutzungskonzentration auf den Parzellen Nrn. 281 und 553 und geordnete Parkierungsanlagen. Gestützt auf diesen Antrag beschloss der Gemeindevorstand Ruschein, eine Änderung des bestehenden Quartierplans auf den Parzellen Nrn. 281, 282, 529 und 553 durchzuführen. Der Einleitungsbeschluss lag vom 22. Juli bis 22. August 2011 öffentlich auf. Dagegen erhoben A._ und B._ Einsprache und rügten gestalterische Elemente der vorgesehenen Überbauung, ohne indessen das Verfahren der Quartierplanänderung als solches oder den Quartierplanperimeter zu beanstanden. Der Gemeindevorstand trat mit Entscheid vom 10. September 2011 auf die Einsprachen nicht ein. Dieser Entscheid ist in Rechtskraft erwachsen. Der Gemeindevorstand liess in der Folge die Quartierplanänderung ausarbeiten. Dieser Plan lag vom 4. November bis 5. Dezember 2011 öffentlich auf. Die von A._ und B._ dagegen erhobenen Einsprachen wies der Gemeindevorstand mit Entscheid vom 9. März 2012 ab und genehmigte den geänderten Quartierplan. Diesen Entscheid fochten A._ und B._ mit Beschwerde vom 30. April 2012 beim Verwaltungsgericht des Kantons Graubünden an. Dieses führte am 18. Oktober 2012 einen Augenschein durch, an welchem A._ und B._ teilnahmen. Mit Urteil vom 23. Oktober 2012 wies das Verwaltungsgericht die Beschwerde ab. B. Mit Eingabe vom 7. Januar 2013 führen A._ und B._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, der angefochtene Entscheid des Verwaltungsgerichts vom 23. Oktober 2012 sei aufzuheben, und es sei festzustellen, dass der Quartierplangenehmigungs- und Einspracheentscheid des Gemeindevorstands Ruschein vom 9. März 2012 sowie die von der Gemeinde Ruschein den Beschwerdegegnern am 31. August 2012 erteilte Baubewilligung für das im geänderten Quartierplan vorgesehene Bauvorhaben nichtig seien. Zugleich ersuchten die Beschwerdeführer darum, der Beschwerde die aufschiebende Wirkung zu erteilen. Dieses Gesuch wies der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts mit Verfügung vom 7. Februar 2013 ab. Mit Verfügung vom 15. April 2013 hiess der Präsident der I. öffentlich-rechtlichen Abteilung das von der C._ AG gestellte Gesuch um Sicherstellung der Parteientschädigung gut und verpflichtete die im Ausland wohnhaften Beschwerdeführer bei der Gerichtskasse eine Sicherstellung von Fr. 3'000.-- in bar zu hinterlegen. Das Verwaltungsgericht und die Gemeinde Ruschein stellen den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die C._ AG beantragt, auf die Beschwerde sei nicht einzutreten, eventualiter sei diese abzuweisen. D._ erklärt, er schliesse sich den Ausführungen der C._ AG an. Die Beschwerdeführer halten in weiteren Eingaben an ihren Anträgen und an ihrem Standpunkt fest. 