Sachverhalt: A. A. und B. C._ erwarben 1995 ein Doppeleinfamilienhaus an der Oberlandstrasse 8 in Künten. Das Gebäude liegt auf der Parzelle Nr. 530 in der Wohnzone; die südöstliche Ecke des Hauses liegt auf der Grenze zur Landwirtschaftszone. Zugunsten der Parzelle Nr. 530 besteht eine Dienstbarkeit ("ausschliessliches und alleiniges Bepflanzungs- und Gestaltungsrecht" an 281 m2 der angrenzenden Parzelle Nr. 244, die der Landwirtschaftszone zugewiesen ist. B. Am 27. März 2014 reichten A. und B. C._ ein nachträgliches Baugesuch für ihre Gartenanlage (Sitzplätze, Pergola, Stützmauern, Gartenzaun etc.) ein, die sich im Wesentlichen auf Parzelle Nr. 244 in der Landwirtschaftszone befindet. Das Aargauer Departement für Bau, Verkehr und Umwelt (BVU) wies das Gesuch am 10. September 2014 ab. Falls keine die Zonenwidrigkeit der Gartengestaltung beseitigende Umzonung des betroffenen Parzellenteils in der anstehenden Teilrevision der Nutzungsplanung zustandekomme, seien die erstellten Bauten und Anlagen der Gartengestaltung (Sitzplätze, Gartenplatten, Zaun, Mäuerchen, Pergola, Treppe, Stützbauten, Holzpodeste, Gerüst etc.) innert einer Frist von drei Monaten ab Rechtskraft der Nichtumzonung zu beseitigen und die betroffene Fläche zu rekultivieren. Der Gemeinderat Künten forderte A. und B. C._ am 10. November 2014 auf, bis zum 20. Februar 2015 ein Umzonungsgesuch einzureichen; ohne ein solches Gesuch werde der Gemeinderat keine Teilrevision der Nutzungsplanung vornehmen und den Rückbau der Bauten verfügen. C. Mit Eingabe vom 12. Dezember 2014 erhoben A. und B. C._ Beschwerde beim Regierungsrat des Kantons Aargau gegen die Entscheide des BVU und des Gemeinderats Künten. Dieser überwies die Sache am 6. Januar 2015 antragsgemäss dem Verwaltungsgericht des Kantons Aargau (Sprungbeschwerde gemäss § 51 des Aargauer Verwaltungsrechtspflegegesetzes vom 4. Dezember 2007 [VRPG/AG; SAR 271.200]). Das Verwaltungsgericht wies die Beschwerde am 25. August 2015 ab und setzte die Frist für die Einreichung eines Umzonungsgesuchs neu fest (drei Monate ab Rechtskraft des verwaltungsgerichtlichen Entscheids). D. Dagegen haben A. und B. C._ am 14. Oktober 2015 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, alle vorinstanzlichen Entscheide seien aufzuheben und die Wiederherstellung des ursprünglichen Zustands sei als verwirkt, evtl. als unverhältnismässig, zu erklären. Eventuell sei die Streitsache zur Durchführung eines Beweisverfahrens und zur Neuentscheidung an die Vorinstanz zurückzuweisen. E. Das Verwaltungsgericht und das BVU haben auf eine Vernehmlassung verzichtet. Der Gemeinderat Künten verweist auf seine Beschwerdeantwort vor Verwaltungsgericht. Die Beschwerdeführer haben nicht repliziert. F. Mit Verfügung vom 10. November 2015 wurde der Beschwerde die aufschiebende Wirkung zuerkannt.