Sachverhalt:
A. A.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.b 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.c 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 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. Mit Urteil vom 1. Dezember 2011 trat das Verwaltungsgericht auf das Gesuch nicht ein. Zur Begründung führte das Verwaltungsgericht 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. Gegen dieses Urteil ist eine Beschwerde beim Bundesgericht hängig, über die separat entschieden wird (Verfahren 1C_42/2012).
C. C.a V._ und W._ führen mit Eingabe vom 30. September 2011 Stimmrechtsbeschwerde gegen den Regierungsratsbeschluss vom 17. August 2011, die Volksabstimmung zu wiederholen. Sie beantragen im Wesentlichen die Aufhebung der Ziffern 6 und 7 des angefochtenen Entscheids und die Rückweisung der Sache an den Regierungsrat zwecks Erwahrung des Ergebnisses der Abstimmung vom 13. Februar 2011 gemäss den entsprechenden Feststellungen des Regierungsrates vom 23. Februar 2011; eventuell ersuchen sie um Rückweisung der Sache an die Vorinstanz zur Neubeurteilung.
C.b Zur Begründung wird vorab geltend gemacht, der Regierungsrat habe prozessual fehlerhaft gehandelt und namentlich seinen Beschluss mangelhaft begründet; damit habe er den Anspruch auf rechtliches Gehör der Beschwerdeführer gemäss Art. 29 Abs. 2 BV sowie Art. 26 Abs. 2 KV/BE verletzt. Gerügt wird sodann die Verletzung der Garantie der politischen Rechte nach Art. 34 BV sowie der kantonalen Bestimmungen über Volkswahlen und -abstimmungen, namentlich des bernischen Gesetzes vom 5. Mai 1980 über die politischen Rechte (GPR; BSG 141.1). Das Eventualbegehren wird damit begründet, der Regierungsrat habe den Sachverhalt unvollständig festgestellt, indem er nicht ergänzende Abklärungen darüber vorgenommen habe, ob es konkrete Hinweise auf Unregelmässigkeiten in den Gemeinden gebe, welche die Stimmzettel vernichteten.
D. In seiner Vernehmlassung vom 2. November 2011 schliesst der Regierungsrat des Kantons Bern auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Zur Begründung führt er sinngemäss aus, aufgrund der nachträglichen Unmöglichkeit einer Nachzählung habe er letztlich keine andere Wahl gehabt, als das verwaltungsgerichtliche Urteil durch eine Wiederholung der Abstimmung umzusetzen, was im Übrigen ohnehin in seiner Kompetenz für die Organisation von Abstimmungen liege. Sodann habe er weder Verfahrensfehler begangen noch den massgeblichen Sachverhalt unvollständig festgestellt.
E. Mit verfahrensleitender Verfügung vom 8. Dezember 2011 behaftete der Präsident der I. öffentlich-rechtlichen Abteilung den Regierungsrat bei seinem dem Bundesgericht gegenüber geäusserten Versprechen, den Abstimmungstermin vom 11. März 2012 zu verschieben, und wies gestützt darauf ein Gesuch der Beschwerdeführer um aufschiebende Wirkung ab.
F. 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.
G. V._ und W._ äusserten sich mit Replik vom 24. Januar 2012 an das Bundesgericht nochmals zur Sache, wobei sie an ihrem Standpunkt festhalten.
H. Am 29. Februar 2012 reichte der Regierungsrat des Kantons Bern eine Duplik ein, worin er ebenfalls im Wesentlichen an seinem Standpunkt festhält, das Rechtsbegehren aber dahingehend änderte, dass die Beschwerde hinsichtlich der Anfechtung der Neuansetzung der Abstimmungswiederholung auf den 11. März 2012 als gegenstandslos abzuschreiben sei, nachdem die Abstimmung inzwischen abgesetzt worden sei.
I. Mit als "Schlussbemerkungen" bezeichneter Eingabe vom 27. März 2012 passten V._ und W._ ihre Rechtsbegehren in dem Sinne an, dass das Verfahren hinsichtlich Ziffer 7 des Regierungsratsbeschlusses vom 13. Februar 2011 wegen der inzwischen erfolgten Absetzung des Abstimmungstermins als gegenstandslos abzuschreiben sei. Ergänzend führen sie aus, die Absetzung der Abstimmung gebe ihnen in der Sache Recht und sei eventuell zumindest im Kostenpunkt zu ihren Gunsten zu berücksichtigen.
J. Beim Bundesgericht ist eine parallele Beschwerde einer politischen Partei sowie weiterer Stimmberechtigter aus dem Kanton Bern mit im Wesentlichen gleichen Anträgen und analoger Begründung hängig (Verfahren 1C_418/2011). Über diese Beschwerde wird separat entschieden.
K. 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.
Erwägungen:
1. 1.1 Mit der Beschwerde nach Art. 82 lit. c BGG kann die Verletzung von politischen Rechten beim Bundesgericht geltend gemacht werden. Von der Beschwerde werden sowohl eidgenössische als auch kantonale und kommunale Stimmrechtssachen erfasst (Art. 88 Abs. 1 BGG). Der Beschwerde unterliegen insbesondere Entscheide von Exekutivbehörden über die Wiederholung einer Abstimmung (vgl. Urteil 1C_395/2010 vom 7. Februar 2011 E. 1.2).
1.2 In kantonalen Angelegenheiten ist die Stimmrechtsbeschwerde gegen Akte letzter kantonaler Instanzen zulässig (Art. 88 Abs. 1 lit. a BGG). Die Pflicht der Kantone, gegen behördliche Entscheide, welche die politischen Rechte der Stimmberechtigten in kantonalen Angelegenheiten verletzen können, ein Rechtsmittel vorzusehen, erstreckt sich nicht auf Akte des Parlaments und der Regierung (Art. 88 Abs. 2 BGG). Da gemäss Art. 93 Abs. 2 GPR in kantonalen Angelegenheiten die Abstimmungsbeschwerde an das kantonale Verwaltungsgericht unzulässig ist gegen Akte (Handlungen und Beschlüsse) des Grossen Rates und des Regierungsrates, steht gegen den angefochtenen Beschluss des Regierungsrates des Kantons Bern vom 17. August 2011 kein kantonales Rechtsmittel, sondern nur direkt die Stimmrechtsbeschwerde an das Bundesgericht offen.
1.3 Das Beschwerderecht steht gemäss Art. 89 Abs. 3 BGG jeder Person zu, die in der betreffenden Angelegenheit stimmberechtigt ist. Ein besonderes (rechtliches) Interesse in der Sache selbst ist nicht erforderlich (vgl. BGE 134 I 172 E. 1.3.3 S. 176). Die Beschwerdeführer sind als im Kanton Bern Stimmberechtigte zur Beschwerde legitimiert.
1.4 Nach Art. 42 Abs. 2 BGG ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Der Beschwerdeführer muss sich wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzen. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (Art. 106 Abs. 1 BGG). Das setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die Begründungsanforderungen von Art. 42 Abs. 2 BGG erfüllt. Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG). Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen (BGE 135 III 127 E. 1.6 S. 130; 134 II 244 E. 2.1 und 2.2 S. 245 f.; je mit Hinweisen).
1.5 Gemäss Art. 95 lit. a, c und d BGG kann in Stimmrechtssachen die Verletzung von Bundesrecht, der kantonalen verfassungsmässigen Rechte sowie der kantonalen Bestimmungen über die politische Stimmberechtigung der Bürger und Bürgerinnen und derjenigen über Volkswahlen und -abstimmungen gerügt werden. Diese Rügen prüft das Bundesgericht frei (vgl. BGE 129 I 185 E. 2 S. 190; 123 I 175 E. 2d/aa S. 178; je mit Hinweisen).
1.6 Streitgegenstand ist einzig der Beschluss des Regierungsrates vom 17. August 2011, die Volksabstimmung über die Teilrevision des Gesetzes über die Besteuerung der Strassenfahrzeuge zu wiederholen und die Abstimmung über den Gesetzesentwurf mit Volksvorschlag neu anzusetzen. Nicht Objekt des vorliegenden Verfahrens bildet hingegen die Frage der Nachzählung. Diese wurde vom Verwaltungsgericht des Kantons Bern rechtskräftig angeordnet und ist hier nicht Streitgegenstand. Ob die Voraussetzungen einer solchen Nachzählung erfüllt sind, ist daher grundsätzlich nicht zu prüfen. Zu entscheiden ist vielmehr ausschliesslich, ob der Regierungsrat rechtmässig gehandelt hat, indem er die Wiederholung der Volksabstimmung beschloss.
1.7 Die Beschwerdeführer beantragten ursprünglich nebst der Aufhebung der Ziffer 6 des angefochtenen Entscheids, worin der Regierungsrat die Abstimmungswiederholung anordnete, auch die Aufhebung von Ziffer 7 des angefochtenen Beschlusses, worin die neue Abstimmung auf den 11. März 2012 angesetzt wurde. Am 11. Januar 2012 hat der Regierungsrat die Abstimmung vom 11. März 2012 abgesetzt. Das aktuelle Interesse der Beschwerdeführer an der Aufhebung von Ziffer 7 des angefochtenen Entscheids ist damit nachträglich weggefallen, weshalb die Beschwerde insoweit als erledigt abzuschreiben ist (vgl. Art. 71 BGG i.V.m. Art. 72 BZP). Das anerkennen auch die Beschwerdeführer, die das fragliche Rechtsbegehren nachträglich entsprechend angepasst haben.
2. Die Beschwerdeführer verlangen eine öffentliche Urteilsberatung durch das Bundesgericht. Eine solche setzt nach Art. 59 Abs. 1 BGG eine mündliche Beratung voraus. Diese wiederum findet gemäss Art. 58 Abs. 1 BGG nur statt, wenn der Abteilungspräsident eine solche anordnet oder ein Richter es verlangt oder wenn sich keine Einstimmigkeit ergibt. Wird auf dem Weg der Aktenzirkulation entschieden, gibt es grundsätzlich keine öffentliche Urteilsberatung (Art. 58 Abs. 2 i.V.m. Art. 59 Abs. 1 BGG e contrario). Vorliegend besteht kein Grund, von dieser Regelung abzuweichen. Allein der politische Charakter der Streitsache und das Interesse der Stimmberechtigten im Kanton Bern am Ausgang des Verfahrens rechtfertigen eine öffentliche Urteilsberatung entgegen der Auffassung der Beschwerdeführer nicht.
3. 3.1 In formeller Hinsicht rügen die Beschwerdeführer, der Regierungsrat habe gegen ihren Anspruch auf rechtliches Gehör nach Art. 29 Abs. 2 BV und Art. 26 Abs. 2 KV/BE verstossen.
3.2 Eine solche Gehörsverletzung sehen die Beschwerdeführer zunächst darin, dass ihnen mit Verfügung des Amts für Zentrale Dienste der Staatskanzlei vom 16. September 2011 nicht die verlangte vollständige, sondern nur eine teilweise Akteneinsicht gewährt worden sei. Die fragliche Akteneinsichtsverfügung hätte jedoch selbständig angefochten werden können und müssen; sie enthält im Übrigen auch eine ausdrückliche Rechtsmittelbelehrung. Die Beschwerdeführer legen nicht dar, weshalb diese falsch oder es ihnen unmöglich oder unzumutbar gewesen sein sollte, das entsprechende Rechtsmittel zu ergreifen. Damit erweist sich die Rüge als unbegründet.
3.3 Sodann machen die Beschwerdeführer geltend, der Regierungsrat habe seinen Beschluss ungenügend begründet. Die Erwägungen in diesem seien zu knapp ausgefallen und kaum nachvollziehbar. Insbesondere äussere er sich nicht dazu, weshalb der Regierungsrat nicht vor dem Verwaltungsgericht die Revision des verwaltungsgerichtlichen Urteils vom 22. Juni 2011 verlangt habe. Der Erwahrungsbeschluss vom 23. Februar 2011 habe überdies keinen Hinweis auf mögliche Beschwerdeverfahren vor dem Verwaltungsgericht enthalten, worin ebenfalls ein Mangel zu sehen sei.
3.3.1 Der Erwahrungsbeschluss vom 23. Februar 2011 bildet hier nicht Streitgegenstand. Abgesehen davon handelt es sich bei der Erwahrung einer Abstimmung nicht um eine eigentliche individuell-konkrete Anordnung im Sinne einer Verfügung, die mit einer Rechtsmittelbelehrung zu versehen ist, sondern um einen selbständigen organisatorischen Hoheitsakt im Rahmen der politischen Rechte, mit dem in erster Linie numerisch das Ergebnis (Stimmenverhältnis) einer Abstimmung zuhanden der Öffentlichkeit und namentlich des Stimmvolks förmlich festgestellt wird. Überdies wird regelmässig festgestellt, dass im Zeitpunkt der Erwahrung keine Beschwerden hängig sind. Wird eine Vorlage angenommen, ermöglicht die Erwahrung grundsätzlich deren Inkraftsetzung (ETIENNE GRISEL, Initiative et référendum populaires, 3. Aufl., 2004, Rz. 293; ZACCARIA GIACOMETTI, Das Staatsrecht der schweizerischen Kantone, 1941, 435 und 439). Der ausdrückliche Vorbehalt allfälliger späterer Stimmrechtsbeschwerden, die noch gar nicht eingereicht sind, zählt allerdings nicht zum notwendigen Inhalt eines Erwahrungsbeschlusses. Schliesslich führt das Fehlen eines entsprechenden Hinweises ohnehin nicht zur Unanfechtbarkeit des Beschlusses.
3.3.2 Weiter genügt die inhaltliche Begründung des regierungsrätlichen Entscheids über die Neuansetzung der Abstimmung den verfassungsrechtlichen Anforderungen. Wie beim Erwahrungsbeschluss handelt es sich um einen selbständigen organisatorischen Hoheitsakt im Rahmen der politischen Rechte, der sich ähnlich wie eine Allgemeinverfügung unter Regelung eines spezifischen Gegenstandes an einen unbestimmten Adressatenkreis richtet. Die Anforderungen an die Begründung können daher nicht gleich hoch sein wie bei einer individuell-konkreten Verfügung, ausser allenfalls für einzelne Personen, die wesentlich schwerwiegender als die übrige Vielzahl der Adressaten betroffen sind (vgl. etwa BGE 121 I 230 E. 2c S. 232 f.; HÄFELIN/MÜLLER/UHLMANN, Allgemeines Verwaltungsrecht, 6. Aufl., 2010, Rz. 925; TSCHANNEN/ZIMMERLI/MÜLLER, Allgemeines Verwaltungsrecht, 3. Aufl., 2009, 279). Eine solche besondere Betroffenheit behaupten und belegen die Beschwerdeführer nicht. Im Übrigen enthält der angefochtene Entscheid in der im Amtsblatt veröffentlichten Fassung eine wenn auch nicht ausführliche, so doch nachvollziehbare Begründung. Er wurde sodann in einer Medienkonferenz und -mitteilung vertieft erklärt, und es finden sich weitere, ausführliche Erläuterungen dazu im Vortrag der Staatskanzlei an den Regierungsrat, in den die Beschwerdeführer Einsicht nehmen konnten. Das muss im vorliegenden Zusammenhang genügen. Den Beschwerdeführern war es denn auch ohne weiteres möglich, den Entscheid des Regierungsrates über die Abstimmungswiederholung sachgerecht anzufechten.
3.3.3 Insbesondere brauchte der Regierungsrat im Entscheid über die Abstimmungswiederholung nicht auszuführen, weshalb er nicht ein Gesuch um Revision des Verwaltungsgerichtsurteils vom 22. Juni 2011 stellte. Weder bildete diese Frage unmittelbar Gegenstand der Neuansetzung der Abstimmung noch hätte es daran etwas zu ändern vermocht, nachdem der Regierungsrat auf Wiederholung der Abstimmung entschieden hatte. Im Übrigen erscheint ohnehin ungewiss, ob der Regierungsrat überhaupt zur Einreichung eines Revisionsgesuchs berechtigt gewesen wäre. Was schliesslich die inhaltliche Frage betrifft, ob ein Revisionsgrund vorgelegen hätte, so war diese bereits in einem von dritter Seite angehobenen Revisionsverfahren vor dem Verwaltungsgericht hängig (vgl. Sachverhalt B.e), weshalb der Regierungsrat mit Grund davon absah, sich dazu zu äussern.
3.3.4 Der angefochtene Entscheid erweist sich damit nicht als ungenügend begründet und verstösst weder gegen Art. 29 Abs. 2 BV noch gegen Art. 26 Abs. 2 KV/BE.
4. 4.1 Das Urteil des Verwaltungsgerichts vom 22. Juni 2011, mit dem dieses die Nachzählung anordnete, ist rechtskräftig. Ziel der vom Verwaltungsgericht angesetzten Nachzählung war nicht, eine festgestellte Unregelmässigkeit zu korrigieren, sondern aufgrund des sehr knappen Resultats durch Überprüfung der ursprünglichen Auszählung sicherzustellen, dass bei der Ermittlung des Abstimmungsergebnisses der wahre Wille der Stimmenden zum Ausdruck kommt. Konkrete Anhaltspunkte auf Unregelmässigkeiten gab es unbestrittenermassen nicht. Das Verwaltungsgericht ging vielmehr davon aus, äusserst knappe Ergebnisse seien stets mit einem Unsicherheitsfaktor verbunden; da immer ein gewisses Fehlerpotenzial bestehe, sei in solchen Fällen eine Nachzählung unerlässlich. Das Verwaltungsgericht stützte sich insoweit auf die neuere bundesgerichtliche Rechtsprechung zu Sachabstimmungen, wie sie insbesondere in BGE 136 II 136 zum Ausdruck kommt. Ab wann von einem äusserst knappen Ergebnis auszugehen ist, lässt die Rechtsprechung bisher zwar offen. Im vorliegenden Fall gaben aber lediglich ein Promille der Stimmen den Ausschlag, was das Verwaltungsgericht als äusserst knapp wertete.
4.2 Freilich ordnete das Verwaltungsgericht nur die Nachzählung und nicht die Wiederholung der Abstimmung an. Dabei muss es logischerweise davon ausgegangen sein, dass eine Nachzählung auch möglich sei. Eine allgemeine Vollzugsanordnung enthält das Urteil des Verwaltungsgerichts nur in dem Sinne, als die Nachzählung im Sinne der Erwägungen verfügt wird. Darin findet sich keine mögliche Alternative, schon gar nicht ausdrücklich diejenige der Abstimmungswiederholung. Die Vermutung, dass die Nachzählung durchführbar sei, erwies sich nachträglich als unzutreffend, nachdem über 5 % der Stimmzettel, nämlich diejenigen von 29 Gemeinden, vernichtet worden waren und demnach nicht mehr ausgewertet werden können. Der Nachzählungsentscheid als solcher wurde freilich nicht angefochten, bildet also nicht Streitgegenstand und steht in diesem Sinne hier nicht direkt in Frage.
4.3 Bevor der angefochtene Entscheid inhaltlich zu prüfen ist, stellt sich die Frage, ob aufgrund der neuen Sachlage der Regierungsrat überhaupt zuständig war, darüber zu entscheiden, wie weiter vorzugehen war, oder ob nicht einzig das Verwaltungsgericht, das den Nachzählungsentscheid getroffen hatte, dazu berufen gewesen wäre, in einem Revisionsverfahren unter Berücksichtigung des Umstands, dass eine Nachzählung nicht mehr möglich ist, nochmals über die bei ihm damals erhobenen Stimmrechtsbeschwerden zu befinden.
4.3.1 Nach Art. 95 lit. b des bernischen Gesetzes vom 23. Mai 1989 über die Verwaltungsrechtspflege (VRPG; BSG 155.21) kann ein rechtskräftiger Entscheid einer Verwaltungsjustizbehörde auf Gesuch hin abgeändert oder aufgehoben werden, wenn die um Revision ersuchende Partei nachträglich erhebliche Tatsachen erfährt oder entscheidende Beweismittel auffindet, die sie im früheren Verfahren nicht anrufen konnte, unter Ausschluss derjenigen, die nach dem fraglichen, inzwischen rechtskräftigen Entscheid entstanden sind.
4.3.2 Dass einige Gemeinden die Stimmzettel vernichtet hatten, wurde tatsächlich erst nach dem verwaltungsgerichtlichen Urteil vom 22. Juni 2011 bekannt. Nicht erstellt ist, ob die Stimmzettel schon vor oder erst nach dem Urteil des Verwaltungsgerichts vernichtet wurden. Zwar ist zu vermuten, dass dies schon vorher stattgefunden hat, der genaue Zeitpunkt müsste aber, soweit dies massgeblich sein sollte, so oder so in einem allfälligen Revisionsverfahren geklärt werden. Kein Hindernis für eine Revision bildet die Kann-Formel in Art 95 VRPG, stellt diese doch die Revision nicht ins Belieben der zuständigen Justizbehörde (MERKLI/AESCHLIMANN/HERZOG, Kommentar zum Gesetz über die Verwaltungsrechtspflege im Kanton Bern, 1997, N. 1 zu Art. 95 VRPG).
4.3.3 Selbst wenn die Möglichkeit eines allfälligen Revisionsverfahrens vor dem Verwaltungsgericht bestünde, schliesst dies die Zuständigkeit des Regierungsrates nicht von vornherein aus, falls von einer eigenständigen Kompetenz desselben auszugehen ist, in welchem Fall sich die Zuständigkeiten überschneiden können (vgl. MERKLI/ AESCHLIMANN/HERZOG, a.a.O., N. 5 zu Art. 95 VRPG). Gemäss Art. 18 Abs. 2 GPR stellt der Regierungsrat aufgrund eines Berichts der Staatskanzlei die Ergebnisse kantonaler Abstimmungen fest (Erwahrung). Nach Art. 67 GPR übt der Regierungsrat die Oberaufsicht über die eidgenössischen und kantonalen Abstimmungen und Wahlen aus (Abs. 1), und er erlässt die zum Vollzug des Gesetzes über die politischen Rechte erforderlichen Verordnungen und Weisungen, setzt die Abstimmungs- und Wahltage fest und erwahrt die Ergebnisse der Abstimmungen und Wahlen, soweit hierfür nicht andere Behörden zuständig sind (Abs. 2). Der Regierungsrat verfügt mithin über eine selbständige Zuständigkeit für die Ansetzung von Abstimmungen und die Anerkennung der sich daraus ergebenden Resultate. Ihm kommt damit auch eine konkrete Verantwortung für die korrekte Ermittlung des wahren Volkswillens zu.
4.3.4 Wie das Verwaltungsgericht in seinem Urteil vom 22. Juni 2011 ausgeführt hat, schliesst Art. 93 Abs. 2 GPR die Beschwerde an das Verwaltungsgericht gegen Akte (Handlungen und Beschlüsse) des Grossen Rates und des Regierungsrates betreffend kantonale Abstimmungen und Wahlen aus, was mit Art. 88 Abs. 2 BGG grundsätzlich vereinbar ist. Dazu zählt an sich auch der Erwahrungsbeschluss. Die Ermittlung der Ergebnisse von kantonalen Abstimmungen mündet jedoch grundsätzlich immer in einen Erwahrungsbeschluss des Regierungsrates. Nach Art. 93 Abs. 1 GPR entscheidet das Verwaltungsgericht über Abstimmungsbeschwerden, mit denen die Ergebnisse einer kantonalen Abstimmung angefochten werden. Das Verwaltungsgericht erachtet daher entsprechende Beschwerden als zulässig und bejahte im vorliegenden Fall gestützt darauf seine eigene Zuständigkeit, ohne sich freilich ausdrücklich zu den damit verknüpften rechtlichen Auswirkungen auf den Erwahrungsbeschluss zu äussern.
4.3.5 Demnach stand es grundsätzlich in der Kompetenz des Regierungsrates, unabhängig von einem Revisionsverfahren, wenn auch durchaus auf der Grundlage des rechtskräftigen verwaltungsgerichtlichen Urteils bzw. in logischer Fortsetzung desselben, eine Abstimmungswiederholung anzuordnen. Im Übrigen kann ein Erwahrungsentscheid auch in Wiedererwägung gezogen werden und es besteht unter Umständen sogar ein Anspruch darauf (vgl. BGE 113 Ia 146). Im vorliegenden Fall wurde der ursprüngliche Erwahrungsbeschluss vom 23. Februar 2011 als Feststellung des Abstimmungsergebnisses (vgl. Art. 18 Abs. 2 GRP) zwar weder vom Regierungsrat noch vom Verwaltungsgericht formell aufgehoben, er verlor aber spätestens mit dem verwaltungsgerichtlichen Urteil vom 22. Juni 2011 jegliche Rechtswirkung, die über die Feststellung des damals ermittelten reinen Stimmenverhältnisses hinausging. Immerhin hatte das Verwaltungsgericht die beiden bei ihm eingereichten Beschwerden ausdrücklich gutgeheissen, wobei in einer Beschwerde nebst dem Begehren auf Nachzählung der Antrag gestellt worden war, "die Abstimmung ... sei aufzuheben", womit nur der Erwahrungsbeschluss bzw. die darin enthaltene Feststellung des Stimmenverhältnisses gemeint sein konnte. Ob das Verwaltungsgericht oder allenfalls der Regierungsrat den Erwahrungsbeschluss formell hätte aufheben müssen, kann hier jedoch offenbleiben. So oder so war es dem Regierungsrat inhaltlich nicht verwehrt, selbständig im Sinne des verwaltungsgerichtlichen Urteils einen Weg zu finden, um die Ermittlung des wahren Volkswillens sicherzustellen, der nach dem Urteil des Verwaltungsgerichts nicht mit dem ausgezählten und damals vom Regierungsrat entsprechend erwahrten Stimmenverhältnis übereinstimmen muss. Aus eigener Kompetenz in Angelegenheiten der Durchführung und Organisation von Wahlen und Abstimmungen oblag es dem Regierungsrat auch ohne ausdrückliche spezifische gesetzliche Grundlage, für die vorliegende Konstellation eine geeignete Lösung zu suchen. Der Regierungsrat war daher auch nicht verpflichtet, anstelle eigenen Handelns selbst ein Revisionsgesuch beim Verwaltungsgericht einzureichen.
4.4 Unter diesen Umständen verbietet es sich aber auch, im umgekehrten Sinne den Beschwerdeführern vorzuhalten, selbst kein Revisionsgesuch beim Verwaltungsgericht gestellt zu haben. Es erscheint schon fraglich, ob sie dazu legitimiert gewesen wären, nachdem sie im ersten verwaltungsgerichtlichen Verfahren nicht Partei gewesen waren. Weil das Verwaltungsgericht auf das bei ihm hängige Revisionsgesuch anderer mit Verweis auf die regierungsrätliche Kompetenz bzw. das entsprechende Parallelverfahren nicht eingetreten ist und soweit eine Wiederholung der Abstimmung gerade nicht von der Revision des verwaltungsgerichtlichen Urteils abhängig gemacht hat, sondern dem Regierungsrat die entsprechende eigenständige Kompetenz zugestanden wird, darf den Beschwerdeführern ohnehin nicht vorgeworfen werden, sie hätten selbst um Revision ersuchen müssen. Aus analogen Gründen kann ihnen auch nicht vorgehalten werden, sie hätten das Urteil des Verwaltungsgerichts vom 22. Juni 2011 direkt beim Bundesgericht anfechten müssen, zumal völlig unklar ist, wann für sie die Frist dafür zu laufen begonnen hätte. Für die Zulässigkeit der Beschwerde vor Bundesgericht wird im Übrigen gemeinhin nicht verlangt, dass von einer Revisionsmöglichkeit Gebrauch gemacht worden ist (vgl. etwa das Urteil 2C_908/2008 vom 23. August 2010, u.a. mit Verweis auf BGE 133 III 439 E. 3.1 S. 444).
4.5 Indem der Regierungsrat selbständig tätig wurde und die Wiederholung der Abstimmung anordnete, handelte er demnach aus eigener Kompetenz. Dies ist mit dem Verfassungsrecht des Bundes (insbesondere Art. 34 BV) und des Kantons Bern vereinbar und verstösst auch nicht gegen das bernische Gesetzes- und Verordnungsrecht in Angelegenheiten der politischen Rechte (Gesetz und Verordnung des Kantons Bern über die politischen Rechte).
5. 5.1 Inhaltlich wurde dem Regierungsrat vom Verwaltungsgericht durch dessen Anordnung, das Ergebnis nachzuzählen, sinngemäss der Auftrag erteilt, zu prüfen, ob der Wille der Stimmbürger durch die Auszählung, die ein äusserst knappes Resultat ergeben hatte, korrekt ermittelt worden war. Der vom Verwaltungsgericht dafür grundsätzlich vorgegebene Weg erwies sich aber nachträglich als ausgeschlossen, weil über 5 % der Stimmzettel bereits vernichtet waren. Es fragt sich, welche rechtlichen Folgen sich daraus ergeben.
5.2 Das bernische Recht enthält keine ausdrückliche Regelung der Frage, wann bzw. unter welchen Voraussetzungen eine Abstimmung wiederholt werden muss. Die Rechtsprechung (vgl. etwa BGE 136 II 132; 131 I 442; 114 Ia 42) und die Fachliteratur (vgl. beispielsweise MICHEL BESSON, Behördliche Information vor Volksabstimmungen, 2003, 390 ff.; HANGARTNER/KLEY, Die demokratischen Rechte in Bund und Kantonen der Schweizerischen Eidgenossenschaft, 2000, 107, Rz. 2560 f.; BÉNÉDICTE TORNAY, La démocratie directe saisie par le juge, 2008, 278 ff.; PIERRE TSCHANNEN, Stimmrecht und politische Verständigung, 1995, 137) setzen sich zwar eingehend mit der Frage auseinander, unter welchen Voraussetzungen eine Nachzählung anzuordnen sei, diese Frage ist aber rechtskräftig entschieden und stellt sich hier grundsätzlich nicht mehr. Zu entscheiden ist mithin einzig, was gilt, wenn sich eine rechtskräftig angeordnete Nachzählung als undurchführbar erweist, wozu sich das Schrifttum kaum äussert (vgl. immerhin VITO PICENONI, Die Kassation von Volkswahlen und Volksabstimmungen, 1945, 109 ff.).
5.3 Der Entscheid des Verwaltungsgerichts über die Anordnung einer Nachzählung beruhte auf BGE 136 II 132. Das Bundesgericht ging darin davon aus, dass aufgrund der plausiblen Erfahrung, dass Zählfehler stets möglich sind, jedes sehr knappe Resultat bei korrekter Zählung kippen könnte. Diese Vermutung lasse sich nur durch Nachzählung widerlegen und sei insofern gleich wie der Verdacht auf Unregelmässigkeiten zu behandeln (vgl. insbes. BGE 136 II 132 E. 2.4.2 S. 137 ff.). Dieser Zusammenhang ergibt sich nicht nur aus dem hier nicht anwendbaren Art. 77 Abs. 1 lit. b des Bundesgesetzes vom 17. Dezember 1976 über die politischen Rechte (BPR; SR 161.1), sondern auch aus dem einschlägigen Verfassungsrecht, insbesondere aus Art. 34 Abs. 2 BV (vgl. MICHEL BESSON, Legitimation zur Beschwerde in Stimmrechtssachen, in: ZBJV 2011, 863 f.). Es liegt hier im Übrigen eine andere Ausgangslage vor als im Fall der eidgenössischen Unternehmungssteuerreform, wo es um die Tragweite einer nachträglich aufgedeckten Unregelmässigkeit bei knappem Ergebnis ging (vgl. BGE 1C_176/2011 vom 20. Dezember 2011), ist doch im Unterschied zu diesem Fall hier eine Nachzählung schon rechtskräftig und damit verbindlich angeordnet. Der vorliegende Fall ist auch nicht vergleichbar mit demjenigen, in dem es um die Frage ging, was bei Stimmengleichheit bei der Nationalratswahl zu gelten habe (vgl. BGE 138 II 5), folgen Wahlen und Sachabstimmungen doch nicht uneingeschränkt denselben Rechtsregeln (vgl. für ein knappes Ergebnis bei Wahlen auch BGE 131 I 442).
5.4 BGE 136 II 132 ist in der Literatur, soweit ersichtlich, bisher nicht auf grundsätzliche Kritik gestossen. Im Gegenteil befürwortet PIERRE TSCHANNEN diesen Entscheid sogar ausdrücklich (PIERRE TSCHANNEN, Staatsrecht der Schweizerischen Eidgenossenschaft, 3. Aufl., 2011, § 52 Rz. 70), führt aber weiter aus (vgl. KÄLIN/KÜNZLI/LIENHARD/ TSCHANNEN/TSCHENTSCHER, Die staatsrechtliche Rechtsprechung des Bundesgerichts in den Jahren 2010 und 2011, in: ZBJV 2011, 808 f.):
"Praktikabel ist der stimmrechtliche Anspruch auf Nachzählung allerdings nur, wenn die erneute Ausmittlung unverzüglich und von Amtes wegen veranlasst wird. Geschieht dies erst auf Beschwerde hin, kann man sicher sein: Die eine oder andere Gemeinde wird die Zettel bereits vernichtet haben. Natürlich muss dann die ganze Abstimmung erneut angesetzt werden, sonst liesse sich jede Nachzählung auf einfachste Weise sabotieren. Eine solche Rechtsfolge allerdings ist unschön, ganz abgesehen davon, dass sich kein Urnengang eins zu eins wiederholen lässt."
Das von TSCHANNEN verwendete Argument der Manipulation zielt auf Handlungen, die darauf gerichtet sind, durch Verunmöglichung der Nachzählung zu erreichen, dass wieder auf das in der ursprünglichen Auszählung ermittelte Stimmenverhältnis zurückgegriffen wird. Die Argumentation lässt sich freilich auch umkehren: Ist die Abstimmungswiederholung unausweichliche Folge der Unmöglichkeit der Nachzählung, so liesse sich die Neuansetzung durch die Vernichtung der Stimmzettel erzwingen. Das Kriterium kann daher nicht allein den Ausschlag geben.
5.5 Ausgangspunkt muss vielmehr sein, dass gemäss der bundesgerichtlichen Rechtsprechung, wie sie hier vom Verwaltungsgericht übernommen und umgesetzt wurde, die Vermutung besteht, die Ermittlung des Volkswillens könne aufgrund des äusserst knappen Stimmenverhältnisses unzutreffend sein, weshalb dieses zu verifizieren sei. Nachdem das Verwaltungsgericht im vorliegenden Fall geurteilt hatte, das festgestellte Abstimmungsergebnis sei als solches ohne weitere Kontrolle nicht gültig, konnte der Regierungsrat nicht mehr darauf abstellen. Auf das ursprüngliche Resultat zurückzukommen, würde nämlich bedeuten, auf ein Ergebnis abzustellen, von dem rechtskräftig festgestellt ist, dass es vermutungsweise an einem erheblichen Mangel leidet. Das ist mit der verfassungsrechtlichen Vorgabe, den Volkswillen korrekt zu ermitteln, was keine entsprechenden Vorbehalte erträgt, nicht vereinbar. Die Überprüfung des Volkswillens ist jedoch grundsätzlich nur auf zwei Wegen möglich, erstens durch Nachzählung, sofern sich eine solche noch durchführen lässt, oder zweitens durch Wiederholung der Abstimmung. Eine solche neue Abstimmung wird zwangsläufig unter anderen Voraussetzungen ablaufen, als sie bei der ersten Abstimmung bestanden hatten und die Folge des Zeitablaufs sind und die verschiedene Faktoren wie insbesondere die Zusammensetzung des Stimmvolks und die politischen Rahmenbedingungen umfassen (vgl. schon BGE 114 Ia 427 E. 8a S. 449). Je länger mit der Neuansetzung zugewartet wird, desto mehr ändern sich tendenziell die Rahmenbedingungen. Einerseits erscheint dies nicht unproblematisch; andererseits ist es ebenfalls im Rahmen einer neuen Vorlage möglich, und es kommt auch vor, dass das Volk über die gleiche Materie wiederholt und unter Umständen mit unterschiedlichem Ausgang abstimmt.
5.6 Im vorliegenden Zusammenhang muss im Vordergrund die angeordnete Überprüfung des Abstimmungsergebnisses stehen, bestünde sonst doch die Gefahr, dass der institutionell bedeutsame Rechtsschutz (dazu etwa GEROLD STEINMANN, in: Ehrenzeller/Mastronardi/Schweizer/Vallender [Hrsg.], Die schweizerische Bundesverfassung, Kommentar, 2. Aufl., Zürich/St. Gallen 2008, N. 5 und 21 ff. zu Art. 34 BV; TSCHANNEN, 1995, a.a.O., 511 ff.) gegen die Ermittlung von Abstimmungsergebnissen wirkungslos bliebe. Das grundsätzliche Ziel, dem wahren Volkswillen soweit wie möglich gerecht zu werden, spricht für eine Abstimmungswiederholung, falls sich die Nachzählung als ausgeschlossen erweist und falls diese wie hier, wo sich das bereits aus dem Grund für die Nachzählung ergibt, zu einem anderen Ergebnis hätte führen können (vgl. PICENONI, a.a.O., 110 f.). Von der Wiederholung der Abstimmung ist einzig abzusehen, wenn überwiegende Gründe dagegen sprechen, was etwa bei klaren Hinweisen auf Manipulationshandlungen - im Nachgang zur Abstimmung, um dadurch eine Wiederholung zu erreichen - zutreffen könnte oder wenn sich die Abstimmungswiederholung als völlig unverhältnismässig erwiese bzw. mit den Anliegen der Rechtssicherheit nicht in Einklang zu bringen wäre (vgl. BGE 114 Ia 427 E. 8 S. 448 ff.). Solche besonderen Umstände liegen hier indessen nicht vor. Weder gibt es Anhaltspunkte für Manipulationen noch erscheint eine Abstimmungswiederholung unverhältnismässig. Auch sonstige Gründe für eine Ausnahme sind nicht ersichtlich. Am rein finanziellen oder organisatorischen Aufwand allein kann es nicht scheitern. Damit erweist sich die Neuansetzung der Abstimmung im vorliegenden Fall als grundsätzlich mit dem Verfassungsrecht vereinbar. Wieweit die fehlbaren Gemeinden allenfalls für die Kosten einstehen müssen, die durch eine Wiederholung der Abstimmung entstehen, ist hier nicht zu entscheiden.
5.7 Es kann sich mithin nur noch fragen, ob die vollständige Wiederholung der Abstimmung zu weit geht und es bei einer Neuansetzung in lediglich beschränktem Umfang sein Bewenden haben muss.
5.7.1 Nur eine Teilwiederholung der Abstimmung in den Gemeinden, in denen die Stimmzettel nicht mehr vorhanden sind, in Kombination mit einer Nachzählung in den übrigen Gemeinden verbietet sich aus Gründen der einheitlichen Ermittlung des Willens des Stimmvolks. Es geht nicht an, die Stimmen aus zwei Abstimmungen, die unter verschiedenen Rahmenbedingungen stattgefunden haben, zusammenzuzählen. Vielmehr muss sich der Gesamtwille des Stimmvolks aus Stimmabgaben ergeben, die gleichzeitig und unter denselben Voraussetzungen zustande gekommen sind.
5.7.2 Im vorliegenden Fall wäre es denkbar, dem Stimmvolk nur die Stichfrage nochmals zu unterbreiten. Einzig in der Stichfrage ergab sich in der Abstimmung vom 13. Februar 2011 ein äusserst knappes Resultat. In den beiden Hauptpunkten war das Ergebnis eindeutig, und dieses wurde von keiner Seite je in Frage gestellt. Theoretisch könnte die Stichfrage unbedeutend werden, sollte in der neuen Abstimmung eine der beiden Vorlagen im Hauptpunkt verworfen werden. Auch lautete das Dispositiv des verwaltungsgerichtlichen Urteils vom 22. Juni 2011 auf Anordnung der Nachzählung im Sinne der Erwägungen, und in E. 5.2 hiess es "... ist erforderlich, dass vorab die Sortierung der Stimmzettel in gültige und ungültige überprüft wird und sodann die Stimmen in der Stichfrage nachgezählt werden". Demgegenüber ordnete der Regierungsrat, nachdem sich die Nachzählung als ausgeschlossen erwiesen hatte, im angefochtenen Entscheid uneingeschränkt die "Wiederholung der Volksabstimmung betreffend Teilrevision des Gesetzes über die Besteuerung der Strassenfahrzeuge mit Volksvorschlag" an. Obwohl der Regierungsratsbeschluss dies nicht näher konkretisiert, kann er nur so verstanden werden, dass die ganze Abstimmung in beiden Hauptpunkten (Gesetz in der Fassung gemäss Parlamentsbeschluss und gemäss Volksvorschlag) sowie in der Stichfrage zu wiederholen ist. Indessen wird von keiner Seite geltend gemacht, der angefochtene Entscheid schiesse in diesem Sinne über das Ziel hinaus und die Wiederholung der Abstimmung sei auf die Stichfrage zu beschränken. Das drängt sich denn auch nicht auf, bilden die beiden Vorlagen doch formell und materiell eine untrennbare Einheit, über die in der neuen Abstimmung auch nochmals integral zu entscheiden ist. Angesichts des Umstands, dass eine Wiederholung der Abstimmung ohnehin unter veränderten Randbedingungen stattfindet, erschiene es sachfremd und damit unverhältnismässig, die Thematik aufzuspalten.
5.8 Der angefochtene Entscheid hält damit auch in der Sache vor dem Verfassungsrecht (insbesondere Art. 34 BV) stand und verstösst zudem nicht gegen die Bestimmungen des Kantons Bern über Volksabstimmungen, namentlich nicht gegen das bernische Gesetz über die politischen Rechte.
6. Schliesslich stellte der Regierungsrat den Sachverhalt nicht unvollständig fest, wie die Beschwerdeführer auch noch geltend machen. Da es für die Frage der Wiederholung der Abstimmung nach rechtskräftig angeordneter, aber nicht mehr möglicher Nachzählung auf das Vorliegen allfälliger Unregelmässigkeiten gar nicht ankommt, musste der Regierungsrat nicht prüfen, ob allenfalls solche Mängel vorlagen.
7. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit sie nicht als erledigt abzuschreiben ist (vgl. E. 1.7).
Bei diesem Verfahrensausgang werden die Beschwerdeführer unter Solidarhaft kostenpflichtig (Art. 66 Abs. 1 und 5, Art. 65 BGG). Das gilt auch, soweit die Beschwerde als erledigt abgeschrieben wird. Zwar wird dem Anliegen der Beschwerdeführer in dem Sinne gefolgt, dass die Abstimmung abgesetzt wurde. In der Sache unterliegen sie aber auch insofern, da es sich im Ergebnis lediglich um eine vorläufige Vorkehr handelt, wie sie ebenfalls durch eine vorsorgliche Massnahme erreicht worden wäre. Die Wiederholung der Abstimmung entfällt indes nicht definitiv, was der Gehalt des ursprünglichen Antrags der Beschwerdeführer war.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit sie nicht gegenstandslos geworden ist (Ziffer 7 des Beschlusses Nr. 1304 des Regierungsrates des Kantons Bern vom 17. August 2011).
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter Solidarhaft auferlegt.
3. Dieses Urteil wird den Beschwerdeführern und dem Regierungsrat des Kantons Bern schriftlich mitgeteilt.
Lausanne, 25. April 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Uebersax