Sachverhalt: A. Am 8. Februar 2005 erteilte die Einwohnergemeinde Walkringen den Eheleuten X._ die Bewilligung für den Neubau eines Einfamilienhauses mit Einstellhalle auf Parzelle Nr. 1474, Grundbuch Walkringen. Die Baubewilligung erwuchs in Rechtskraft. Am 13. November 2006 stellten Gemeindeorgane fest, dass die Eheleute X._ entlang der Parzellengrenze zur Zihlstrasse am Fahrbahnrand Granitblöcke als Bordsteine aufstellten. Am 16. November 2006 verfügte die Baupolizeibehörde der Einwohnergemeinde Walkringen die Einstellung der Bauarbeiten und forderte die Bauherrschaft auf, diese Bauarbeiten rückgängig zu machen. Am 25. November 2006 reichten die Eheleute X._ ein nachträgliches Baugesuch für die Vorplatzgestaltung ein und ersuchten um Erteilung einer Ausnahmebewilligung für das Unterschreiten des Lichtraumprofils der Strasse, das nach Art. 68 Abs. 1 des Gesetzes vom 2. Februar 1964 über Bau und Unterhalt der Strassen (Strassenbaugesetz, SBG/BE; BSG 732.11) in der Regel 50 cm beträgt. Mit Verfügung vom 11. Januar 2007 verweigerte die Einwohnergemeinde die Ausnahmebewilligung nach Art. 68 SBG/BE. Nachdem die Eheleute X._ am 18. Januar 2007 hiergegen Beschwerde bei der Bau-, Verkehrs- und Energiedirektion des Kantons Bern erhoben hatten, erliess die Einwohnergemeinde Walkringen am 24. Januar 2007 eine korrigierte Verfügung, in der sie der Bauherrschaft Frist bis 31. März 2007 ansetzte, um die Stützmauer an der Strassengrenze zu entfernen oder sie um 50 cm vom Strassenrand zurückzuversetzen. Die Bau-, Verkehrs- und Energiedirektion schrieb darauf das bei ihr eingeleitete Beschwerdeverfahren ab. B. Gegen die Verfügung vom 24. Januar 2007 erhoben die Eheleute X._ am 26. Februar 2007 erneut Beschwerde bei der Bau-, Verkehrs- und Energiedirektion. Sie beantragten, die Wiederherstellungsverfügung sei aufzuheben und ihnen sei eine Ausnahmebewilligung für das Unterschreiten des Lichtraumprofils zu erteilen. Am 13. September 2007 wies die Bau-, Verkehrs- und Energiedirektion die Beschwerde ab. Das Verwaltungsgericht des Kantons Bern wies mit Urteil vom 13. Mai 2008 eine gegen diesen Entscheid erhobene Verwaltungsgerichtsbeschwerde von den Eheleuten X._ ab, soweit es darauf eintrat. Es setzte eine neue Frist von zwei Monaten ab Rechtskraft des Urteils zur Entfernung bzw. Rückversetzung der strittigen Bordsteinmauer an. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. Juni 2008 beantragen die Eheleute X._, das Urteil des Verwaltungsgerichts des Kantons Bern vom 13. Mai 2008 sei aufzuheben und die Sache sei zu neuer Beurteilung im Sinne der Erwägungen des Bundesgerichts an die Vorinstanz zurückzuweisen. D. Die Bau-, Verkehrs- und Energiedirektion verzichtet auf Vernehmlassung. Das Verwaltungsgericht und die Einwohnergemeinde Walkringen schliessen auf Abweisung der Beschwerde. Die Eheleute X._ halten in einer weiteren Eingabe an ihrer Beschwerde fest. Am 8. Oktober 2008 reicht die Einwohnergemeinde Walkringen unaufgefordert eine zusätzliche Eingabe ein. Die Eheleute X._ beantragen mit Schreiben vom 9. Oktober 2008, diese Eingabe aus den Akten zu weisen. E. Der Präsident der I. öffentlich-rechtlichen Abteilung hat der Beschwerde mit Verfügung vom 15. Juli 2008 aufschiebende Wirkung beigelegt. 