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. 