Sachverhalt: A. Am 19. November 2009 beschloss der Grosse Rat des Kantons Bern eine Änderung des Gesetzes über die Besteuerung der Strassenfahrzeuge vom 12. März 1998 (BSFG; BSG 761.611). Inhaltlich bezweckt die auch als "ECOTAX-Vorlage" bezeichnete Gesetzesrevision, die Rahmenbedingungen für eine ökologischere Motorfahrzeugsteuer zu schaffen. Namentlich sollen besonders verbrauchs-, energie- und emissionseffiziente Fahrzeuge steuerlich begünstigt, ineffiziente hingegen mit einem Zuschlag belastet werden. Sodann soll durch eine moderate, generelle Senkung des Grundsteueransatzes dem Umstand Rechnung getragen werden, dass der Kanton Bern im gesamtschweizerischen Vergleich die höchsten Fahrzeugsteuern aufweist. Diese Gesetzesänderung hätte am 1. Januar 2011 in Kraft treten sollen. A.a Am 16. April 2010 reichte ein von X._ organisiertes "Komitee für eine gerechte Strassenverkehrssteuer im Kanton Bern" einen Volksvorschlag (konstruktives Referendum) gemäss Art. 63 Abs. 3 der Verfassung des Kantons Bern vom 6. Juni 1993 (KV/BE; SR 131.212) ein, der unter Übernahme der Grundsätze der parlamentarischen Vorlage abweichende Vorschläge zu einzelnen Punkten vorsieht wie insbesondere eine stärkere generelle Steuersenkung, eine Halbierung der Gebühren für Garagenschilder, den Wegfall des Malus sowie eine modifizierte Regelung des Bonus. A.b Der Grosse Rat erklärte den Volksvorschlag für gültig und unterbreitete ihn zusammen mit seiner eigenen Gesetzesvorlage am 13. Februar 2011 der Volksabstimmung. In dieser wurden, gemäss den entsprechenden Feststellungen des Regierungsrates vom 23. Februar 2011, sowohl die Vorlage des Grossen Rates (mit 172'427 Ja-Stimmen gegen 154'792 Nein-Stimmen) als auch der Volksvorschlag (mit 166'860 Ja-Stimmen gegen 164'325 Nein-Stimmen) angenommen. In der Stichfrage (vgl. Art. 63 Abs. 4 i.V.m. Art. 60 Abs. 2 KV/BE) erzielte der Volksvorschlag 165'977 Stimmen und die Vorlage des Grossen Rates 165'614 Stimmen; der Volksvorschlag obsiegte demnach mit einem Vorsprung von 363 Stimmen bzw. von 0,1 % (oder von einem Promille) aller Stimmen. B. B.a Gegen die Abstimmung gingen beim Verwaltungsgericht des Kantons Bern zwei Beschwerden (mit Eingabe vom 21. Februar 2011 von Q._ und mit solcher vom 2. März 2011 von Z._) ein. Im Wesentlichen wurde dabei beantragt, aufgrund des äusserst knappen Abstimmungsresultats seien die abgegebenen Stimmzettel nachzuzählen. Mit Urteil vom 22. Juni 2011 hiess das Verwaltungsgericht die Beschwerden gut und ordnete die Nachzählung der kantonalen Volksabstimmung an. Dieses Urteil blieb unangefochten und wurde rechtskräftig. B.b In der Folge beauftragte der Regierungsrat des Kantons Bern am 6. Juli 2011 die Staatskanzlei, die Stimmzettel der kantonalen Volksabstimmung vom 13. Februar 2011 am 26. und 27. August 2011 nachzuzählen. Daraufhin wurden der Staatskanzlei bis zum 10. August 2011 30 Gemeinden gemeldet, die ihre Stimmzettel in der Zwischenzeit vernichtet hatten. Diese Handlungen hatten stattgefunden, obwohl Art. 42 Abs. 3 der Verordnung über die politischen Rechte vom 10. Dezember 1980 des Kantons Bern (VPR; BGS 141.112) die Gemeinden verpflichtet, Stimmzettel für jede Kategorie gesondert verpackt und versiegelt an einem sicheren Ort bei der Gemeindeverwaltung aufzubewahren und sie erst nach der rechtskräftigen Erledigung allfälliger Beschwerden zu vernichten. B.c Am 17. August 2011 stellte der Regierungsrat gestützt auf einen entsprechenden Vortrag der Staatskanzlei fest, dass insgesamt 18'095 Stimmzettel fehlten, was 5,46 % aller Stimmzettel entspricht. Eine Gemeinde fand ihre Stimmzettel offenbar später wieder, womit sich die Zahl der fehlbaren Gemeinden auf 29 bzw. das Manko auf 5,37 % aller Stimmzettel reduzierte. B.d Im gleichen Beschluss vom 17. August 2011 stellte der Regierungsrat fest, dass eine ordnungsgemässe Nachzählung der Stimmzettel, wie das Verwaltungsgericht dies in seinem Urteil vom 22. Juni 2011 gefordert hatte, wegen der beachtlichen Anzahl vernichteter Stimmzettel nicht mehr möglich sei. Der Regierungsrat hob daher in Ziffer 5 seines Beschlusses die Anweisung an die Staatskanzlei zur Nachzählung der Stimmen auf und verfügte stattdessen in Ziffer 6 seines Beschlusses, dass die Volksabstimmung über die Teilrevision des Gesetzes über die Besteuerung der Strassenfahrzeuge zu wiederholen sei, setzte in Ziffer 7 seines Beschlusses die Abstimmung über den Gesetzesentwurf mit Volksvorschlag auf den 11. März 2012 an und beauftragte die Staatskanzlei, die notwendigen Massnahmen zu ergreifen. Dieser Beschluss wurde am 31. August 2011 mit Rechtsmittelbelehrung im Amtsblatt des Kantons Bern publiziert. B.e Gegen diesen Beschluss sind beim Bundesgericht eine Stimmrechtsbeschwerde der Schweizerischen Volkspartei (SVP) des Kantons Bern, von Y._ und X._ (Verfahren 1C_418/2011) sowie eine zweite Beschwerde weiterer Stimmberechtigter aus dem Kanton Bern (Verfahren 1C_420/2011) hängig. Beantragt wird im Wesentlichen die Aufhebung der Ziffern 6 und 7 des angefochtenen Beschlusses; zudem sei der Regierungsrat anzuweisen, den Verzicht auf die Abstimmungswiederholung zu erklären und das Ergebnis der Volksabstimmung gemäss den entsprechenden Feststellungen des Regierungsrates vom 23. Februar 2011 zu erwahren. Über diese Beschwerden wird separat entschieden. B.f Mit Beschluss vom 9. September 2010 revidierte der Grosse Rat des Kantons Bern das Datum des Inkrafttretens der Novelle des Gesetzes über die Besteuerung der Strassenfahrzeuge ein erstes Mal und passte die in den Vorlagen enthaltenen Einführungsdaten wegen der erfolgten Zeitverzögerung so an, dass die Gesetzesänderung am 1. Januar 2012 hätte in Kraft treten können. Am 21. November 2011 setzte er das Inkrafttreten in einem weiteren entsprechenden Beschluss auf den 1. Januar 2013 an. Gegen diesen zweiten Beschluss ist ebenfalls eine Beschwerde beim Bundesgericht hängig (Verfahren 1C_16/2012), über die separat entschieden wird. C. C.a Am 29. September 2011 stellten die Schweizerische Volkspartei (SVP) des Kantons Bern, Y._ und X._ beim Verwaltungsgericht des Kantons Bern ein Gesuch um Revision des Urteils vom 22. Juni 2011, worin sie im Wesentlichen beantragten, aufgrund der nicht mehr vollständigen Stimmzettel sei auf eine Nachzählung zu verzichten und die Ergebnisse der Volksabstimmung vom 13. Februar 2011 seien zu bestätigen. C.b Mit Urteil vom 1. Dezember 2011 trat das Verwaltungsgericht auf das Gesuch nicht ein. Zur Begründung führte es im Wesentlichen aus, die erhobene Kritik richte sich nicht gegen das angefochtene verwaltungsgerichtliche Urteil, sondern gegen die vom Regierungsrat angeordnete Wiederholung der Volksabstimmung. Den entsprechenden Regierungsratsbeschluss könnten die Gesuchsteller aber selbständig beim Bundesgericht mit Beschwerde in öffentlich-rechtlichen Angelegenheiten anfechten, weshalb sie kein aktuelles praktisches Interesse an einer Revision des Verwaltungsgerichtsurteils hätten. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 20. Januar 2012 an das Bundesgericht beantragen die Schweizerische Volkspartei (SVP) des Kantons Bern, Y._ und X._, das Revisionsurteil des Verwaltungsgerichts vom 1. Dezember 2011 aufzuheben und die Sache zur neuen Beurteilung im Sinne der Erwägungen an dieses zurückzuweisen. Gerügt wird eine Verletzung der Legitimationsvorschriften des kantonalen Gesetzes vom 23. Mai 1989 über die Verwaltungsrechtspflege (VRPG; BSG 155.21) und des bernischen Gesetzes vom 5. Mai 1980 über die politischen Rechte (GPR; BSG 141.1) in einer Angelegenheit betreffend die politische Stimmberechtigung, weil das Verwaltungsgericht auf das bei ihm eingereichte Revisionsgesuch der Beschwerdeführer mangels Legitimation zu Unrecht nicht eingetreten sei. Die aufgeworfenen Rechtsfragen könnten sich jederzeit wieder stellen, weshalb das Revisionsgesuch auch trotz allenfalls fehlenden praktischen Interesses hätte behandelt werden müssen. Zugleich würden dadurch Art. 111 Abs. 1 und Art. 89 Abs. 3 BGG verletzt, weil die Beschwerdebefugnis vor der kantonalen Instanz nicht enger umschrieben werden dürfe als vor Bundesgericht. Sodann laufe der Nichteintretensentscheid auf eine formelle Rechtsverweigerung hinaus und verstosse gegen den Grundsatz von Treu und Glauben, womit er Art. 5 Abs. 3 sowie Art. 9 und 29 BV verletze. E. Der Regierungsrat und das Verwaltungsgericht des Kantons Bern schliessen in ihren Stellungnahmen vom 29. bzw. 22. Februar 2012 auf Abweisung der Beschwerde. Der am Verfahren vor dem Verwaltungsgericht beteiligte Z._ hat sich innert Frist nicht vernehmen lassen. F. Der Regierungsrat äusserte sich am 27. März 2012 unter grundsätzlichem Festhalten an seinem Standpunkt nochmals zur Eingabe des Verwaltungsgerichts. G. Am 11. Januar 2012 beschloss der Regierungsrat des Kantons Bern mit Blick auf die hängigen Beschwerden, die Abstimmung vom 11. März 2012 abzusetzen, worüber die Öffentlichkeit entsprechend informiert wurde.