Sachverhalt:
A. X._ reiste im Oktober 2000 unter der Identität von Z._, Staatsangehöriger von Burundi, illegal in die Schweiz ein und ersuchte um Asyl. Das Gesuch wurde im Oktober 2001 vom Bundesamt für Flüchtlinge abgewiesen und der Gesuchsteller aus der Schweiz weggewiesen. Die Schweizerische Asylrekurskommission bestätigte diesen Entscheid mit Urteil vom 11. Februar 2002. X._ galt seit Juli 2002 als verschwunden.
Im August 2004 meldete sich X._ bei den Einwohnerdiensten, Migration und Fremdenpolizei der Stadt Bern, die ihm aufgrund einer vorgewiesenen echten französischen Identitätskarte (ausgestellt im Mai 2002) sowie eines Arbeitsvertrages eine Aufenthaltsbewilligung EG/EFTA erteilten. Nach einem entsprechenden Hinweis von Interpol Brüssel überprüfte die Stadtpolizei Bern die Identitätsausweise von X._. Anlässlich einer Hausdurchsuchung am 4. Juli 2007 wurden in dessen Wohnung unter anderem ein französischer Reisepass und ein Geburtsregisterauszug des Ministère des Départements et Territoires d'Outre-Mer vom April 2006 sichergestellt. Das französische Generalkonsulat in Zürich teilte der Stadtpolizei Bern am 7. Juli 2007 mit, bei den Dokumenten, die X._ zur Erlangung der Identitätskarte bzw. des Reisepasses vorgewiesen habe - ein certificat de nationalité française vom 16. Juli 1996 bzw. einen Geburtsregisterauszug -, handle es sich um Fälschungen; zugleich ersuchte es um Zustellung der Identitätskarte sowie des Reisepasses zur Annullierung. Am 21. August 2007 kamen die Einwohnerdienste diesem Ersuchen nach und am 9. Juni 2008 widerriefen sie nach Gewährung des rechtlichen Gehörs die Aufenthaltsbewilligung von X._. Dessen dagegen gerichtete Beschwerde wurde von der Polizei- und Militärdirektion des Kantons Bern abgewiesen. Auch seiner Beschwerde ans Verwaltungsgericht des Kantons Bern blieb der Erfolg versagt (Urteil vom 2. Februar 2010).
B. Mit Verfügung vom 11. März 2008 eröffnete das Generalkonsulat X._, die commision électorale siégeant au ministère des affaires étrangères et européennes habe ihn von Amtes wegen von der Liste der im Ausland wohnenden französischen Wähler gestrichen, wogegen er direkt Rekurs beim tribunal d'instance du 1er arrondissement de Paris einreichen könne. Ob ein Rekurs eingereicht worden ist, ergibt sich nicht aus den Akten.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt X._ dem Bundesgericht, das Urteil des Verwaltungsgerichts des Kantons Bern vom 2. Februar 2010 aufzuheben und festzustellen, dass die Bewilligungsvoraussetzungen gemäss Freizügigkeitsabkommen erfüllt und er demzufolge aufenthaltsberechtigt sei.
Die Einwohnerdienste, Migration und Fremdenpolizei der Stadt Bern, die Polizei- und Militärdirektion sowie das Verwaltungsgericht des Kantons Bern und das Bundesamt für Migration beantragen, die Beschwerde abzuweisen.

Erwägungen:
1. Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
Sollte der Beschwerdeführer französischer Staatsangehöriger sein, könnte er allenfalls gestützt auf das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.142.112.681) einen Rechtsanspruch auf Erteilung einer Aufenthaltsbewilligung geltend machen (vg. Urteil 2C_531/2009 vom 22. Juni 2010 E. 2.2). Auf die Beschwerde ist daher grundsätzlich einzutreten.
2. 2.1 Das Freizügigkeitsabkommen räumt den Staatsangehörigen der Vertragsparteien ein gegenseitiges Recht auf Aufenthalt und Zugang zu einer Erwerbstätigkeit (Art. 4) bzw. auf erwerbslosen Aufenthalt ein (Art. 6). Gemäss Art. 2 Abs. 1 Anhang I FZA haben die Staatsangehörigen einer Vertragspartei das Recht, sich nach Massgabe der Kapitel II bis IV im Hoheitsgebiet der anderen Vertragspartei aufzuhalten und dort eine Erwerbstätigkeit auszuüben.
2.2 Gemäss Art. 1 Abs. 1 Anhang I FZA können die Vertragsstaaten zwar einen gültigen Personalausweis oder einen Reisepass verlangen; dies kann jedoch nicht zur Verweigerung des Aufenthalts führen, wenn die Staatsangehörigkeit anderswie nachgewiesen werden kann (Urteile des EuGH vom 25. Juli 2002 in der Rechtssache C-459/99, Mouvement contre le racisme, l'antisémitisme et la xénophobie [MRAX], Slg. 2002, I-6591, Randnrn. 76 und 80; sowie vom 17. Februar 2005 in der Rechtssache C-215/03, Oulane, Slg. 2005, I-1215, Rdnrn. 21-26; in gleicher Weise das Bundesgericht im Urteil 2A.494/2003 vom 24. August 2004, E. 4.3).
3. Der Beschwerdeführer macht geltend, ihm sei mit dem Vorgehen der Behörden die französische Staatsbürgerschaft aberkannt worden, ohne dass ihm dies direkt oder mit einer beschwerdefähigen Verfügung mitgeteilt worden sei. Dieser de-facto Entscheid widerspreche fundamentalsten rechtsstaatlichen Anforderungen und dürfe von der Schweiz nicht anerkannt werden; ihm sei weder das rechtliche Gehör noch Akteneinsicht gewährt worden. Er weist darauf hin, dass er im französischen Staatsbürgerschaftsrecht keine Grundlage für den Entzug der Staatsbürgerschaft infolge Täuschung habe finden können, weshalb der entsprechende Realakt nichtig sei. Es gebe zudem keine Belege dafür, dass das französische Konsulat die eigenen Rechtsvorschriften eingehalten habe. <ref-law> sei daher analog anzuwenden und der Entzug der Staatsbürgerschaft dürfe nicht anerkannt werden.
4. Nach den Feststellungen der Vorinstanz hat das französische Generalkonsulat in Zürich nach entsprechenden Nachforschungen bei den zuständigen französischen Behörden erklärt, diese Überprüfungen hätten ergeben, dass sowohl der Ausweis "certificat de nationalité française" vom 16. Juli 1996, ausgestellt in Noumea, - gestützt auf welchen die Sous-Préfecture du Havre am 29. Mai 2002 die beim Beschwerdeführer eingezogene französische Identitätskarte ausgestellt hat - sowie der "Extrait d'acte de naissance" vom 5. April 2006, ausgestellt durch das Ministère des Départements et Territoires d'Outre-Mer - welchen der Beschwerdeführer zur Erlangung des am 15. Mai 2006 durch das französische Generalkonsulat in Zürich ausgestellten französischen Reisepasses zusätzlich vorgewiesen hat - Fälschungen seien. Die beiden echten Dokumente müssten daher für ungültig erklärt werden ("annulés").
Der Beschwerdeführer hat die Sachverhaltsfeststellungen der Vorinstanz ausdrücklich als zutreffend erklärt.
5. Nach französischem Recht erhalten Kinder die französische Staatsbürgerschaft bei Geburt, wenn zumindest ein Elternteil zum Zeitpunkt der Geburt im Besitz der französischen Staatsbürgerschaft ist, unabhängig davon, ob das Kind in Frankreich oder im Ausland geboren wird (vgl. www.eu-info.de/static/common/files/save/1278/franzstaat.pdf und www.botschaft-frankreich.de/spip.php?article1611). Rechtsgrund für die Erlangung der beiden eingezogenen Dokumente, die dem Beschwerdeführer die französische Staatsangehörigkeit bescheinigen, bildete denn auch nach den Akten eine Geburtsurkunde, nach welcher der Beschwerdeführer als Kind von französischen Eltern in Noumea ("territoire français d'outre-mer") geboren worden sein soll. Der Ausstellung einer Identitätskarte bzw. eines Reisepasses kommt unter diesen Umständen keine die französische Staatsbürgerschaft begründende (konstitutive) Wirkung zu; sie hat lediglich deklaratorischen Charakter.
Auch nach schweizerischem Recht wird das Schweizer Bürgerrecht von Gesetzes wegen durch Geburt erworben, sofern eines der verheirateten Eltern oder die Mutter Schweizer Bürger ist (Art. 1 Abs. 1 des Bundesgesetzes vom 29. September 1952 über Erwerb und Verlust des Schweizer Bürgerrechts [BüG; SR 141.0]). Das Bestehen des Schweizer Bürgerrechts muss durch diejenige Person, die sich darauf berufen will, strikte nachgewiesen werden (vgl. <ref-ruling>). Dieser Nachweis wird in erster Linie durch die Geburtsurkunde zu erbringen sein.
6. 6.1 Die Vorinstanz hat zutreffend erkannt, der Beschwerdeführer müsse den Nachweis erbringen, dass er Staatsangehöriger eines Mitgliedstaates sei; nötigenfalls habe er sich zwecks Beschaffung gültiger Ausweispapiere mit den zuständigen Behörden seines Heimatstaates in Verbindung zu setzen; dies ergebe sich sowohl nach nationalem Recht (Art. 13 und 89 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20] i.V.m. Art. 8 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit [VZAE; SR 142.201]) als auch nach dem Recht der Europäischen Union. Der Beschwerdeführer habe jedoch keine neuen Dokumente beigebracht, die ihn als Staatsangehörigen eines EU-Mitgliedstaates ausweisen würden. Es bestünden keine Anhaltspunkte dafür, dass der Einzug der Ausweispapiere durch das französische Generalkonsulat nicht rechtmässig bzw. im Sinne von <ref-law> Ordre public-widrig wäre. Der Beschwerdeführer könne sich somit mangels Nachweises der Staatsangehörigkeit nicht auf das Freizügigkeitsabkommen berufen, weshalb eine Verlängerung der Aufenthaltsbewilligung EG/EFTA ausser Betracht falle (E. 4.3).
6. 6.1 Die Vorinstanz hat zutreffend erkannt, der Beschwerdeführer müsse den Nachweis erbringen, dass er Staatsangehöriger eines Mitgliedstaates sei; nötigenfalls habe er sich zwecks Beschaffung gültiger Ausweispapiere mit den zuständigen Behörden seines Heimatstaates in Verbindung zu setzen; dies ergebe sich sowohl nach nationalem Recht (Art. 13 und 89 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20] i.V.m. Art. 8 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit [VZAE; SR 142.201]) als auch nach dem Recht der Europäischen Union. Der Beschwerdeführer habe jedoch keine neuen Dokumente beigebracht, die ihn als Staatsangehörigen eines EU-Mitgliedstaates ausweisen würden. Es bestünden keine Anhaltspunkte dafür, dass der Einzug der Ausweispapiere durch das französische Generalkonsulat nicht rechtmässig bzw. im Sinne von <ref-law> Ordre public-widrig wäre. Der Beschwerdeführer könne sich somit mangels Nachweises der Staatsangehörigkeit nicht auf das Freizügigkeitsabkommen berufen, weshalb eine Verlängerung der Aufenthaltsbewilligung EG/EFTA ausser Betracht falle (E. 4.3).
6.2 6.2.1 Zu Recht hat die Vorinstanz zunächst darauf hingewiesen, dass sich der Beschwerdeführer nur ungenügend bemüht habe, Auskünfte bzw. eine anfechtbare Verfügung zu erlangen. Die von ihm erstmals mit der vorliegenden Beschwerde eingereichte schriftliche Anfrage an das Generalkonsulat vom 10. Juli 2009, die lediglich aus drei Zeilen besteht, kann nicht als ernsthafte Anstrengung bezeichnet werden; dies erst recht, nachdem er seit der ebenfalls nun erst eingelegten Antwort des Generalkonsulats vom 31. Juli 2009, er werde in den nächsten Wochen eine Bestätigung des Passentzuges erhalten, nichts mehr unternommen hat.
6.2.2 Die dem Beschwerdeführer unbestrittenermassen aufgrund von Fälschungen ausgestellten echten Ausweisschriften begründen als solche nicht die französische Staatsbürgerschaft. Sie bestätigen lediglich die durch die Geburt (belegt durch die Geburtsurkunde) und damit bereits von Gesetzes wegen begründete Staatsbürgerschaft. Da nach dem Dargelegten von einer gefälschten Geburtsurkunde auszugehen ist, ist damit der Rechtsgrund für die Ausstellung dieser Ausweise entfallen. Ob mit der Ungültigerklärung der Ausweise dem Beschwerdeführer eine allfällige Staatsbürgerschaft entzogen wurde, ohne dass dafür im französischen Recht eine Grundlage bestünde, kann offen bleiben. Denn das Recht gewährt grundsätzlich dem missbräuchlich Handelnden für Rechtspositionen, die er durch Täuschung erwirkt hat, in der Regel keinen Bestandesschutz (vgl. <ref-ruling> E. 2; PIERRE TSCHANNEN UND ANDERE, Allgemeines Verwaltungsrecht, 3. Aufl., 2009, § 31 N 38 und 57). Auch nach schweizerischem Recht werden Pass und Identitätskarte zwingend entzogen, wenn die Voraussetzungen für deren Ausstellung nicht oder nicht mehr erfüllt sind oder wenn sie falsche Eintragungen enthalten (Art. 7 des Bundesgesetzes vom 22. Juni 2001 über Ausweise für Schweizer Staatsangehörige [SR 143.1]). Von einer Verletzung des schweizerischen Ordre public durch die Ungültigerklärung kann demnach nicht die Rede sein.
6.2.3 Entscheidend ist im vorliegenden Fall, dass der Beschwerdeführer bisher keinen neuen Nachweis der französischen Staatsbürgerschaft erbracht hat. Er bringt auch in seiner Beschwerde nichts vor, was darauf schliessen lassen könnte, dass er rechtmässig im Besitz der französischen Staatsbürgerschaft wäre. Er behauptet weder, französischer Staatsbürger zu sein, noch dass die von ihm zur Erlangung der beiden eingezogenen Ausweispapiere vorgelegten Urkunden echt seien. Aufgrund des vorliegenden Sachverhaltes besteht vielmehr die Vermutung, dass der Beschwerdeführer nicht französischer Staatsbürger ist. Da er den gegenteiligen Beweis bisher nicht erbracht hat, durfte die Vorinstanz von dieser Vermutung ausgehen (vgl. <ref-ruling> E. 3).
6.3 Es ist somit bundesrechtlich nicht zu beanstanden, wenn die Vorinstanz unter diesen Umständen zum Schluss gekommen ist, der Beschwerdeführer könne sich mangels Nachweises der Staatsangehörigkeit eines EU-Mitgliedstaates nicht auf das Freizügigkeitsabkommen berufen.
7. Der Beschwerdeführer rügt eine Verletzung seines Anspruches auf rechtliches Gehör bzw. auf Akteneinsicht und Erlass einer beschwerdefähigen Verfügung.
Was er in diesem Zusammenhang vorbringt, betrifft das Vorgehen des französischen Generalkonsulates in Zürich sowie der französischen Behörden, weshalb darauf nicht näher einzugehen ist. Seitens der Vorinstanzen wurde ihm das rechtliche Gehör mehrfach gewährt. Damit erweist sich die Beschwerde auch in diesem Punkt als unbegründet.
8. Die Beschwerde ist aus diesen Gründen abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens hat der Beschwerdeführer die Kosten des Verfahrens vor Bundesgericht zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Bern sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 4. Oktober 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Küng