Sachverhalt: A. X._ ist Eigentümer der in der Landwirtschaftszone liegenden Parzelle Nr. 2055 in Brienz. Nordwestlich grenzt diese an die bewaldete Parzelle Nr. 122, die im Eigentum der Schwellenkorporation Aareboden steht. Am 30. August 2004 reichte X._ bei der Einwohnergemeinde Brienz ein Baugesuch ein für die Umnutzung der bestehenden landwirtschaftlichen Halle in eine Lager- und Einstellhalle mit einer Werkstatt für den eigenen Gewerbebetrieb. Im Rahmen dieses Baubewilligungsverfahrens stellte er erstmals 2006 und nochmals im Jahr 2010 ein nachträgliches Rodungsgesuch für eine Zufahrt über Parzelle Nr. 122. Gegen das Vorhaben erhob u.a. die Schwellenkorporation Aareboden Einsprache. Am 9. Dezember 2011 erteilte das Regierungsstatthalteramt Interlaken-Oberhasli die Baubewilligung und eröffnete die Ausnahmebewilligung für das Bauen ausserhalb der Bauzone gemäss Verfügung des Amts für Gemeinden und Raumordnung des Kantons Bern (AGR) vom 6. Juli 2009. Dagegen wies das Regierungsstatthalteramt das Rodungsgesuch ab und verpflichtete X._, die widerrechtlich erstellte Zufahrt auf Parzelle 122 zurückzubauen und das Gelände wieder aufzuforsten. B. Hiergegen erhob X._ erfolglos Beschwerde bei der Bau-, Verkehrs- und Energiedirektion des Kantons Bern (BVE) und anschliessend Beschwerde beim Verwaltungsgericht des Kantons Bern, mit dem Antrag, es sei auf die Wiederherstellung des rechtmässigen Zustands auf Parzelle Nr. 122 zu verzichten, und statt dessen sei er zu verpflichten, auf der Parzelle Nr. 3202 "Harstettli" eine Fläche von 324 m2 wieder aufzuforsten. Das Verwaltungsgericht wies die Beschwerde am 7. Januar 2013 ab, soweit es darauf eintrat. C. Dagegen hat X._ am 13. Februar 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und auf die Wiederherstellung des ursprünglichen Zustands sei zu verzichten. D. Die Schwellenkorporation Aareboden schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei. Die BVE hat auf eine Vernehmlassung verzichtet. Das BAFU legt in seiner Vernehmlassung dar, dass die kantonalen Behörden nach Art. 50 Abs. 2 des Bundesgesetzes über den Wald vom 4. Oktober 1991 (WaG; SR 921.0) zur Beseitigung rechtswidriger Zustände und somit zur Anordnung der Wiederherstellung des rechtmässigen Zustands verpflichtet seien. Die vom Bundesgericht festgelegte Verwirkungsfrist von 30 Jahren (BGE 105 Ib 265 E. 6b S. 271) sei noch nicht abgelaufen; die Wiederherstellung könne auch in keiner Weise als unverhältnismässig betrachtet werden. E. In seiner Replik hält der Beschwerdeführer an seinen Anträgen fest.