Sachverhalt:
A. Am 13. Juni 2008 beschloss die Bundesversammlung die Genehmigung und die Umsetzung des Notenaustauschs zwischen der Schweiz und der Europäischen Gemeinschaft betreffend die Übernahme der Verordnung (EG) Nr. 2252/2004 über biometrische Pässe und Reisedokumente. Gegen diesen Bundesbeschluss wurde das Referendum ergriffen. An der Volksabstimmung vom 17. Mai 2009 wurde der Bundesbeschluss mit 953'136 Ja-Stimmen (50.14 %) gegen 947'632 Nein-Stimmen (49.86 %) angenommen.
Mit Eingabe vom 21. Mai 2009 erhob Christoph Meyer beim Regierungsrat des Kantons Basel-Stadt Abstimmungsbeschwerde gemäss Art. 77 Abs. 1 lit. b des Bundesgesetzes vom 17. Dezember 1976 über die politischen Rechte (BPR; SR 161.1). Er beantragte im Wesentlichen, die Abstimmung im Kanton Basel-Stadt sei für ungültig zu erklären und erneut durchzuführen. Eventualiter sei eine Neuauszählung der Stimmen vorzunehmen. Der Regierungsrat wies die Beschwerde mit Beschluss vom 2. Juni 2009 ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 7. Juni 2009 beantragt Christoph Meyer, der Beschluss des Regierungsrats sei aufzuheben und die Stimmzettel seien neu zu prüfen und auszuzählen.
Der Regierungsrat beantragt in seiner Stellungnahme vom 1. Juli 2009 die Abweisung der Beschwerde. Die ebenfalls zur Stellungnahme eingeladene Bundeskanzlei liess sich nicht vernehmen.
C. Die I. öffentlich-rechtliche Abteilung des Bundesgerichts hat die Angelegenheit am 1. Oktober 2009 an einer öffentlichen Sitzung beraten.

Erwägungen:
1. 1.1 Mit der Beschwerde nach <ref-law> kann die Verletzung von politischen Rechten geltend gemacht werden. Von der Beschwerde werden sowohl eidgenössische als auch kantonale und kommunale Stimmrechtssachen erfasst (<ref-law>). Das Beschwerderecht steht gemäss <ref-law> jeder Person zu, die in der betreffenden Angelegenheit stimmberechtigt ist. Der Regierungsrat ist Vorinstanz im Sinne von <ref-law>. Die gestellten Anträge sind im Lichte von <ref-law> zulässig.
1. 1.1 Mit der Beschwerde nach <ref-law> kann die Verletzung von politischen Rechten geltend gemacht werden. Von der Beschwerde werden sowohl eidgenössische als auch kantonale und kommunale Stimmrechtssachen erfasst (<ref-law>). Das Beschwerderecht steht gemäss <ref-law> jeder Person zu, die in der betreffenden Angelegenheit stimmberechtigt ist. Der Regierungsrat ist Vorinstanz im Sinne von <ref-law>. Die gestellten Anträge sind im Lichte von <ref-law> zulässig.
1.2 1.2.1 Im Verfahren vor dem Regierungsrat hatte der Beschwerdeführer in erster Linie beantragt, das Abstimmungsresultat des Kantons Basel-Stadt sei für ungültig zu erklären und die Abstimmung erneut durchzuführen. Falls die Abstimmung nicht für ungültig erklärt werde, sei eine Neuauszählung vorzunehmen. Seine Anträge hatte der Beschwerdeführer nebst einer Reihe von Unregelmässigkeiten namentlich mit dem knappen gesamtschweizerischen Abstimmungsergebnis begründet. Im Beschwerdeverfahren vor Bundesgericht hält er nur noch den Eventualantrag aufrecht, die Stimmzettel der kantonalen Abstimmung seien neu zu prüfen und auszuzählen, und begründet diesen ausschliesslich mit dem knappen gesamtschweizerischen Ergebnis. Der Beschwerdeführer rügt eine Verletzung von <ref-law>, des Bundesgesetzes über die politischen Rechte, von Art. 11 der Verordnung vom 24. Mai 1978 über die politischen Rechte (SR 161.11) und von § 79 des Gesetzes des Kantons Basel-Stadt vom 21. April 1994 über Wahlen und Abstimmungen (Wahlgesetz; SG 132.100). Er vertritt die Ansicht, im Falle eines knappen Abstimmungsresultats müsse die erfahrungsgemässe Fehlerquote bei der Ergebnisermittlung berücksichtigt werden und ein Hinweis auf darüber hinausgehende Unregelmässigkeiten sei entbehrlich. Abzustellen sei bei einer eidgenössischen Abstimmung auch auf das gesamtschweizerische Resultat. Verschiedene Kantone würden Bestimmungen kennen, wonach eine Nachzählung bei knappem Abstimmungsausgang automatisch zu erfolgen habe. Das Bundesgesetz über die politischen Rechte weise diesbezüglich eine Lücke auf, die in Anlehnung an diese kantonalen Bestimmungen zu schliessen sei. Für eine Nachzählung spreche auch der Grundsatz der Verhältnismässigkeit (<ref-law>), denn bei der Abstimmung sei es um Belange gegangen, welche wesentliche Grundrechte berührten.
1.2.2 Unter Verweisung auf Art. 11 der Verordnung über die politischen Rechte und § 79 Abs. 1 des kantonalen Wahlgesetzes erwog der Regierungsrat, dass Nachzählungen anzuordnen seien, wenn der Verdacht bestehe, dass ein Ergebnis unrichtig sei bzw. sofern stichhaltige Gründe vorlägen, welche die zuverlässige Ermittlung des Ergebnisses infrage stellten. Mit der Behauptung, dass der Streubereich gemäss Statistikern bei 1 % liege, habe der Beschwerdeführer nicht dargetan, dass im Kanton Basel-Stadt falsch gezählt worden sei, und er mache auch keinen stichhaltigen Grund für eine Nachzählung geltend.
1.2.3 Das basel-städtische Abstimmungsresultat - der Unterschied zwischen den Ja-Stimmen (24'929) und den Nein-Stimmen (25'859) betrugt 930 Stimmen bzw. 1,83 % - war nicht knapp und bot insoweit in der Tat keinen Anlass zu einer Nachzählung. Zudem vermöchte selbst eine erhebliche Änderung des basel-städtischen Ergebnisses das (eidgenössische) Hauptresultat mit einer Differenz von 5'504 Stimmen nicht zu beeinflussen. Indem der Beschwerdeführer seinen Antrag auf Nachzählung des kantonalen Abstimmungsresultats ausschliesslich mit dem knappen (gesamtschweizerischen) Hauptresultat begründet, bringt er ein Argument vor, welches zum vornherein nicht rechtserheblich ist. Insofern ist seine Beschwerde nicht hinreichend begründet und kann darauf nicht eingetreten werden (<ref-law>).
Eine Nachzählung aufgrund eines knappen (eidgenössischen) Hauptresultats müsste in allen Kantonen erfolgen, unabhängig davon, wie das jeweilige kantonale Resultat ausfiel. Solches hat aber der Beschwerdeführer vorliegend nicht verlangt, weder im kantonalen noch im bundesgerichtlichen Verfahren. Auf seine das knappe (eidgenössische) Hauptresultat betreffenden Ausführungen ist deshalb mangels eines Begehrens nicht einzutreten (<ref-law>).
2. Auf die Beschwerde ist nicht einzutreten. Es ist gerechtfertigt, keine Gerichtskosten zu erheben (<ref-law>). Der Beschwerdeführer hat keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Es werden keine Gerichtskosten erhoben.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, dem Regierungsrat des Kantons Basel-Stadt und der Bundeskanzlei schriftlich mitgeteilt.
Lausanne, 1. Oktober 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold