Sachverhalt: A. X._ und Y._ sind je zur Hälfte Miteigentümer der Parzelle Nr. 1536, Rossfall, Urnäsch, auf welcher das Gasthaus "Rossfall" (Assek. Nr. 424) steht. Das Gasthaus verfügt über einen Saaltrakt im nördlichen Gebäudeteil, in welchem seit vielen Jahren die Sennenbälle stattfinden. Dieser Saaltrakt wurde im Jahre 1981 durch eine Gasexplosion stark beschädigt. Beim Wiederaufbau wurden am Saaltrakt hinterlüftete Holzschindelschirme angebracht, welche rasch anfaulten und in der Folge gestützt auf eine Baubewilligung des Planungsamtes des Kantons Appenzell Ausserrhoden vom 1. September 2003 strassen- und wetterseitig gegen Westen und Norden hin durch je einen Eternitschindelschirm ersetzt wurden. Der Holzschindelschirm an der Ostfassade des Saaltrakts blieb unverändert bestehen. Der Südtrakt des Gasthauses mit Gaststube, Wohnung und Terrasse wurde bei der Gasexplosion weniger stark beschädigt. Er weist strassenseitig eine herkömmliche gestemmte Holztäferfassade auf. Auch auf der Südfassade bestand bis zum Jahr 2006 ein herkömmlicher, nicht hinterlüfteter Holzschindelschirm. Die Ostfassade des Südtraktes ist mit Holzschindeln verkleidet. Gegen den Saaltrakt hin geht die Ostfassade in einen gemauerten Fassadenteil (Kreuzfirst) über. Das Gasthaus Rossfall liegt in der Landwirtschaftszone. Überdies befindet es sich in der kantonalen Landschaftsschutzzone und ist im kantonalen Schutzzonenplan von 1991 als Ganzes als "Kulturobjekt ausserhalb der Bauzone Nr. 1.9" verzeichnet. Dieser von der Baudirektion erlassene kantonale Schutzzonenplan lag vom 3. Juni bis zum 2. Juli 1991 öffentlich auf und wurde in der Folge rechtskräftig. B. X._ und Y._ ersuchten am 11. Januar 2006 um die Baubewilligung für die Sanierung der Südfassade des Gasthaus- und Wohntraktes der Liegenschaft Rossfall mittels Eternitschindeln. Das Planungsamt des Kantons Appenzell Ausserhoden erteilte am 17. März 2006 gestützt auf Art. 24c RPG (SR 700) und Art. 42 RPV (SR 700.1) die raumplanerische Bewilligung mit der Auflage, dass anstelle der vorgesehenen Eternitschindeln Holzschindeln anzubringen seien. Diesen Entscheid des Planungsamtes fochten die genannten beiden Miteigentümer zusammen mit der Baubewilligung der Baubewilligungskommission Urnäsch vom 21. März 2006, in welcher die genannte Auflage des Planungsamtes bestätigt wurde, beim kantonalen Departement für Bau und Umwelt an. Sie beantragten, es sei ihnen die Verkleidung der Südfassade mit demselben Eternitschiefer zu bewilligen, wie er an der Nord- und Westfassade des wieder aufgebauten Saaltraktes bewilligt worden sei. Anlässlich des am 6. Juni 2006 durchgeführten Augenscheins stellte das Departement für Bau und Umwelt fest, dass die Holzschindeln an der Südfassade entfernt und entgegen der Auflage im angefochtenen Bauentscheid bereits durch Eternitschindeln ersetzt worden sind. Mit Entscheid vom 15. August 2006 wies das Departement für Bau und Umwelt den Rekurs im Sinne der Erwägungen ab und bestimmte, die Eternitschindeln an der Südfassade des Gasthauses Rossfall seien zu entfernen und innert dreier Monate durch Holzschindeln zu ersetzen. C. X._ und Y._ zogen diesen Rekursentscheid an das Verwaltungsgericht des Kantons Appenzell Ausserhoden weiter, welches die Beschwerde mit Urteil vom 27. Juni 2007 abwies. Es hielt im Wesentlichen fest, das Departement für Bau und Umwelt habe für die ohne Bewilligung an der Südfassade des Gasthauses Rossfall angebrachte Eternitverkleidung zu Recht die nachträgliche Baubewilligung verweigert. Der widerrechtlich vorgenommene Materialwechsel und die Aufgabe der herkömmlichen Fassadengliederung mit Eck-Pilastern seien mit den für dieses Kulturobjekt in der Landschaftsschutzzone geltenden Schutz- und Gestaltungsbestimmungen unvereinbar. Die angeordnete Wiederherstellung des rechtmässigen Zustands sei rechtlich zulässig und insbesondere auch verhältnismässig. D. Gegen dieses Urteil des Verwaltungsgerichts führen X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht. Sie beantragen, das Urteil des Verwaltungsgerichts, der Entscheid des Departements Bau und Umwelt sowie Ziff. 2 des Bauentscheides des kantonalen Planungsamtes seien aufzuheben und das kantonale Planungsamt sei anzuweisen, die Ausführung der Fassadenerneuerung an der Südfassade des Gebäudes Assek. Nr. 424 mit Eternitschindeln zu bewilligen. Eventualiter sei das Urteil des Verwaltungsgerichts vom 27. Juni 2007 aufzuheben und die Sache zur Neubeurteilung an diese Instanz zurückzuweisen. E. Mit Präsidialverfügung vom 6. Juni 2008 wurde der Beschwerde aufschiebende Wirkung beigelegt. F. Das Departement Bau und Umwelt beantragt, die Beschwerde sei abzuweisen. Das Verwaltungsgericht ersucht um Abweisung der Beschwerde, soweit darauf einzutreten sei. In weiteren Eingaben halten die Beschwerdeführer, das Departement Bau und Umwelt und das Verwaltungsgericht an ihren Standpunkten fest. 