Sachverhalt:
A. X._, geboren 1969, stammt aus dem Kosovo. Ende Mai 1993 gelangte er in die Schweiz und ersuchte hier um Asyl. Das Gesuch wurde abgelehnt. X._ kam der Pflicht, bis zum 15. März 1994 auszureisen, nicht nach. Am 29. Juli 1994 heiratete er eine Schweizerin. Gestützt darauf erhielt er eine Aufenthaltsbewilligung.
Am 11. Juni 1998 stellte X._ ein Gesuch um erleichterte Einbürgerung. Im Einbürgerungsverfahren unterzeichneten er und seine Ehefrau am 12. Februar 1999 eine Erklärung, wonach sie in stabiler ehelicher Gemeinschaft zusammenlebten und weder Trennungs- noch Scheidungsabsichten bestünden. Gleichzeitig nahmen sie zur Kenntnis, dass die erleichterte Einbürgerung nicht möglich sei, wenn vor oder während des Einbürgerungsverfahrens einer der Ehegatten die Trennung oder Scheidung beantragt habe oder keine tatsächliche eheliche Gemeinschaft mehr bestehe. Am 23. Februar 1999 wurde X._ das Schweizer Bürgerrecht verliehen.
Am 27. Mai 1999 reichten die Ehegatten ein gemeinsames Begehren auf Scheidung ein. Am 27. August 1999 wurde die Ehe nach <ref-law> in der Fassung vom 10. Dezember 1907 (AS 24 S. 233) geschieden. Am 3. Dezember 1999 heiratete X._ wieder. Seine neue Frau brachte fünf Tage darauf ein gemeinsames Kind zur Welt. Nach Angaben von X._ gingen aus dieser Ehe seither drei weitere Kinder hervor.
Mit Schreiben vom 17. Juli 2003 teilte das Bundesamt für Zuwanderung, Integration und Auswanderung (IMES, heute: Bundesamt für Migration, BFM) X._ mit, es erwäge, die erleichterte Einbürgerung für nichtig zu erklären. X._ erhielt Gelegenheit zur Stellungnahme. Seine geschiedene Ehefrau äusserte sich vorerst unaufgefordert brieflich gegenüber dem Bundesamt und wurde später noch mündlich einvernommen. Das dabei verfasste Protokoll wurde X._ zur Kenntnis gebracht. In der Folge holte das Bundesamt die Zustimmung des Heimatkantons Bern zur Nichtigerklärung der erleichterten Einbürgerung ein. Mit Verfügung vom 20. Februar 2004 erklärte es die erleichterte Einbürgerung für nichtig.
X._ focht diese Verfügung an. Mit Urteil vom 19. Juni 2008 wies das Bundesverwaltungsgericht seine Beschwerde ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 30. Juli 2008 beantragt X._ im Wesentlichen, das Urteil des Bundesverwaltungsgerichts sei aufzuheben. Eventualiter sei das Urteil aufzuheben und die Sache zur Abklärung des Sachverhalts an die Vorinstanz zurückzuweisen. Subeventualiter sei festzustellen, dass die Kinder des Beschwerdeführers das Schweizer Bürgerrecht behalten.
Das Bundesamt und das Bundesverwaltungsgericht haben auf eine Stellungnahme verzichtet. Mit Präsidialverfügung vom 1. September 2008 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Die Beschwerde richtet sich gegen einen Entscheid in öffentlich-rechtlichen Angelegenheiten des Bundesverwaltungsgerichts (Art. 82 lit. a, Art. 86 Abs. 1 lit. a BGG). Die Ausnahme der ordentlichen Einbürgerungen gemäss <ref-law> erstreckt sich nicht auf die Nichtigerklärung der Einbürgerung. Es liegt auch keine der übrigen Ausnahmen gemäss <ref-law> vor. Auf die Beschwerde ist deshalb grundsätzlich einzutreten.
1.2 Der Beschwerdeführer beantragt subeventualiter, es sei festzustellen, dass seine vier Kinder das Schweizer Bürgerrecht behalten.
Im Zeitpunkt der Nichtigerklärung hatte der Beschwerdeführer mit seiner neuen Ehefrau zwei Kinder. Das Bundesamt lehnte es damals ab, bezüglich dieser beiden Kinder eine Ausnahmeverfügung im Sinne von Art. 41 Abs. 3 des Bürgerrechtsgesetzes vom 29. September 1952 (BüG, SR 141.0) zu erlassen. Nach dieser Bestimmung erstreckt sich die Nichtigkeit auf alle Familienglieder, deren Schweizer Bürgerrecht auf der nichtigerklärten Einbürgerung beruht, sofern nicht ausdrücklich anders verfügt wird. Seit der Nichtigerklärung sind nach Angaben des Beschwerdeführers aus dieser neuen Ehe zwei weitere Kinder hervorgegangen.
Das genannte Begehren bringt der Beschwerdeführer erstmals im bundesgerichtlichen Verfahren vor. Da es neu im Sinne von <ref-law> ist, kann darauf nicht eingetreten werden. Bezüglich der beiden Kinder, welche erst nach der Nichtigerklärung zur Welt kamen und deshalb in die Verfügung nicht einbezogen wurden, fehlt es zudem an einem Anfechtungsobjekt gemäss <ref-law> bzw. an einem Entscheid einer in Art. 86 Abs. 1 genannten Vorinstanz. Insoweit ist auf das Begehren auch deshalb nicht einzutreten.
2. 2.1 Die Vorinstanz legt dar, dass der Beschwerdeführer auf die Abweisung seines Asylgesuchs hin nicht ausgereist sei, sondern eine Schweizerin geheiratet habe. Unmittelbar nach Erfüllung der zeitlichen Voraussetzungen von <ref-law> habe er ein Gesuch um erleichterte Einbürgerung gestellt. Am 23. Februar 1999 sei diese gewährt worden und nur gut drei Monate später hätten die Ehegatten ein gemeinsames Scheidungsbegehren eingereicht. Mit seiner späteren Frau habe er vermutlich zwischen Anfang und Mitte März 1999 ein Kind gezeugt. Der zeitliche Ablauf dieser Ereignisse führe zur tatsächlichen Vermutung, dass bereits im Zeitpunkt der erleichterten Einbürgerung kein beidseitiger, auf die Zukunft gerichteter Ehewille mehr bestanden habe.
Der Beschwerdeführer räumt ein, dass es in seiner Ehe Probleme gegeben habe, macht jedoch geltend, der Ehewille habe im Zeitpunkt der Erklärung noch bestanden. Er und seine Frau hätten sich psychologisch betreuen lassen, was bei einer bloss formell bestehenden Ehe nicht denkbar sei. Die Ursachen für die Schwierigkeiten seien in der Vergangenheit zu finden. Seine Frau sei als Kind sexuell missbraucht worden und sei, nachdem ihr dies im Rahmen der Therapie bewusst geworden sei, nicht mehr in der Lage gewesen, mit ihm sexuell zu verkehren. Er habe zu seiner Ehefrau gehalten. Im März 1999 sei er ihr jedoch untreu geworden und dieser einmalige Seitensprung habe ungewollt zu einer Schwangerschaft geführt. Dass sich die ehelichen Probleme gerade im Frühling 1999 verschlimmert hätten, sei schlicht ein Zufall gewesen. Die Ehefrau habe sich im Mai 1999 für eine Trennung entschieden, da sie der Meinung gewesen sei, dass sie und ihr Mann als Ehepaar "nicht mehr funktionierten".
Der Beschwerdeführer räumt ein, dass es in seiner Ehe Probleme gegeben habe, macht jedoch geltend, der Ehewille habe im Zeitpunkt der Erklärung noch bestanden. Er und seine Frau hätten sich psychologisch betreuen lassen, was bei einer bloss formell bestehenden Ehe nicht denkbar sei. Die Ursachen für die Schwierigkeiten seien in der Vergangenheit zu finden. Seine Frau sei als Kind sexuell missbraucht worden und sei, nachdem ihr dies im Rahmen der Therapie bewusst geworden sei, nicht mehr in der Lage gewesen, mit ihm sexuell zu verkehren. Er habe zu seiner Ehefrau gehalten. Im März 1999 sei er ihr jedoch untreu geworden und dieser einmalige Seitensprung habe ungewollt zu einer Schwangerschaft geführt. Dass sich die ehelichen Probleme gerade im Frühling 1999 verschlimmert hätten, sei schlicht ein Zufall gewesen. Die Ehefrau habe sich im Mai 1999 für eine Trennung entschieden, da sie der Meinung gewesen sei, dass sie und ihr Mann als Ehepaar "nicht mehr funktionierten".
2.2 2.2.1 Gemäss <ref-law> kann ein Ausländer nach der Eheschliessung mit einer Schweizer Bürgerin ein Gesuch um erleichterte Einbürgerung stellen, wenn er insgesamt fünf Jahre in der Schweiz gewohnt hat, seit einem Jahr hier wohnt und seit drei Jahren in ehelicher Gemeinschaft mit der Schweizer Bürgerin lebt. Das Bundesgericht geht davon aus, dass eine eheliche Gemeinschaft im Sinne von <ref-law> nicht nur das formelle Bestehen einer Ehe, sondern das Vorliegen einer tatsächlichen Lebensgemeinschaft voraussetzt. Eine solche Gemeinschaft kann nur bejaht werden, wenn der gemeinsame Wille zu einer ehelichen Gemeinschaft intakt ist. Gemäss konstanter Praxis muss sowohl im Zeitpunkt der Gesuchseinreichung als auch im Zeitpunkt des Einbürgerungsentscheids eine tatsächliche Lebensgemeinschaft bestehen, die Gewähr für die Stabilität der Ehe bietet. Zweifel bezüglich eines dahin gehenden Willens sind angebracht, wenn kurze Zeit nach der erleichterten Einbürgerung die Trennung erfolgt oder die Scheidung eingeleitet wird. Der Gesetzgeber wollte dem ausländischen Ehegatten einer Schweizer Bürgerin die erleichterte Einbürgerung ermöglichen, um die Einheit des Bürgerrechts der Ehegatten im Hinblick auf ihre gemeinsame Zukunft zu fördern (<ref-ruling> E. 2 S. 483 f. mit Hinweisen).
2.2.2 Nach <ref-law> kann die Einbürgerung vom Bundesamt mit Zustimmung der Behörde des Heimatkantons innert fünf Jahren nichtig erklärt werden, wenn sie durch falsche Angaben oder Verheimlichung erheblicher Tatsachen erschlichen worden ist. Das blosse Fehlen der Einbürgerungsvoraussetzungen genügt nicht. Die Nichtigerklärung der Einbürgerung setzt vielmehr voraus, dass diese "erschlichen", d.h. mit einem unlauteren und täuschenden Verhalten erwirkt worden ist. Arglist im Sinne des strafrechtlichen Betrugstatbestands ist nicht erforderlich, wohl aber, dass der Betroffene bezüglich erheblicher Tatsachen bewusst falsche Angaben macht bzw. die Behörde bewusst in einem falschen Glauben lässt (<ref-ruling> E. 3.1 S. 114 f. mit Hinweisen).
2.2.3 In verfahrensrechtlicher Hinsicht richtet sich die erleichterte Einbürgerung nach den Bestimmungen des Bundesgesetzes über das Verwaltungsverfahren (Art. 1 Abs. 1 und Abs. 2 lit. a VwVG). Danach obliegt der Behörde, den Sachverhalt von Amtes wegen festzustellen (Untersuchungsgrundsatz, <ref-law>). Bei der Nichtigerklärung einer erleichterten Einbürgerung ist deshalb von der Behörde zu untersuchen, ob die Ehe im massgeblichen Zeitpunkt der Gesuchseinreichung und der Einbürgerung tatsächlich gelebt wurde.
Im Wesentlichen geht es dabei um innere Vorgänge, die der Behörde oft nicht bekannt und schwierig zu beweisen sind. Sie kann sich daher veranlasst sehen, von bekannten Tatsachen (Vermutungsbasis) auf unbekannte (Vermutungsfolge) zu schliessen. Bei diesen sogenannten tatsächlichen Vermutungen handelt es sich um Wahrscheinlichkeitsfolgerungen, die auf Grund der Lebenserfahrung gezogen werden (<ref-ruling> E. 3.2 S. 485 f.).
Zudem entbindet der Untersuchungsgrundsatz den Rechtsuchenden nicht davon, seinerseits zur Feststellung des Sachverhalts beizutragen. Eine derartige Mitwirkungspflicht der Parteien besteht unter anderem in Verfahren, welche sie durch ihr Begehren einleiten (<ref-law>). Hierzu gehört auch das Gesuch um erleichterte Einbürgerung nach <ref-law>. Klärt die Behörde die Partei darüber auf, worin die Mitwirkungspflicht besteht und welche Tragweite ihr zukommt, so gilt sie selbst dann, wenn sich die Auskunft zum Nachteil des Rechtsunterworfenen auswirkt (<ref-ruling> E. 3.2 S. 115 mit Hinweisen). Die Mitwirkungspflicht gilt gerade für solche Tatsachen, welche eine Partei besser kennt als die Behörden und welche diese ohne Mitwirkung der Betroffenen gar nicht oder nicht mit vernünftigem Aufwand erheben können (<ref-ruling> E. 2b S. 365 mit Hinweis; vgl. auch <ref-ruling> unveröffentlichte E. 4.1 mit Hinweisen).
Zudem entbindet der Untersuchungsgrundsatz den Rechtsuchenden nicht davon, seinerseits zur Feststellung des Sachverhalts beizutragen. Eine derartige Mitwirkungspflicht der Parteien besteht unter anderem in Verfahren, welche sie durch ihr Begehren einleiten (<ref-law>). Hierzu gehört auch das Gesuch um erleichterte Einbürgerung nach <ref-law>. Klärt die Behörde die Partei darüber auf, worin die Mitwirkungspflicht besteht und welche Tragweite ihr zukommt, so gilt sie selbst dann, wenn sich die Auskunft zum Nachteil des Rechtsunterworfenen auswirkt (<ref-ruling> E. 3.2 S. 115 mit Hinweisen). Die Mitwirkungspflicht gilt gerade für solche Tatsachen, welche eine Partei besser kennt als die Behörden und welche diese ohne Mitwirkung der Betroffenen gar nicht oder nicht mit vernünftigem Aufwand erheben können (<ref-ruling> E. 2b S. 365 mit Hinweis; vgl. auch <ref-ruling> unveröffentlichte E. 4.1 mit Hinweisen).
2.3 2.3.1 Umstritten ist, ob der Beschwerdeführer im Zeitpunkt der Einbürgerung einen intakten Ehewillen besass. Da lediglich gut drei Monate später die Ehegatten ein gemeinsames Scheidungsbegehren einreichten, ist zu vermuten, dass dies nicht zutraf. Es ist Sache des Betroffenen, Sachumstände aufzuzeigen, die es als nachvollziehbar erscheinen lassen, dass eine angeblich noch wenige Monate zuvor bestehende tatsächliche, ungetrennte eheliche Gemeinschaft in der Zwischenzeit dergestalt in die Brüche gegangen ist, dass es zur Scheidung kam (<ref-ruling> E. 3.2 S. 486).
2.3.2 Der Beschwerdeführer macht zunächst geltend, dass trotz der Beziehungsprobleme der Ehewille im Zeitpunkt der Einbürgerung weiterbestanden habe. Beide Gatten seien indessen in einer psychisch derart instabilen Verfassung gewesen, dass sie ihren Willen zur Weiterführung der Ehe nicht hätten umsetzen können.
Es trifft im Grundsatz zu, dass eine Ehe trotz bestehender Beziehungsprobleme als intakt bezeichnet werden kann, insbesondere wenn sich die Ehegatten bemühen, die Probleme zu überwinden. Der Beschwerdeführer verkennt jedoch, dass Verwaltungs- und Gerichtsbehörden im Verfahren der Nichtigerklärung der erleichterten Einbürgerung nicht umhin können, von objektiv feststellbaren Umständen auf die Bewusstseinslage und den Willen des Beschwerdeführers zu schliessen. Wenn objektive Umstände auf seit längerem andauernde, gravierende Eheprobleme hinweisen und die Überlebensfähigkeit der Ehe im Zeitpunkt der Einbürgerung als fraglich erscheint, ist es wie bereits dargelegt am Beschwerdeführer aufzuzeigen, weshalb er dennoch Grund hatte, auf die Beständigkeit der Ehe zu vertrauen. Der blosse Hinweis, dass die Ehegatten trotz aller Schwierigkeiten am Willen, die Ehe weiterzuführen, festhielten, reicht dafür nicht. Wenn der Beschwerdeführer einwendet, dass er in der Erklärung für das Bundesamt nicht nach ehelichen Problemen, sondern nach einer tatsächlichen ehelichen Beziehung gefragt worden sei, verkennt er diese Zusammenhänge.
Hinzu kommt ein weiterer Umstand, der gegen die Darstellung des Beschwerdeführers spricht. Vermutlich in der ersten Hälfte des Monats März 1999 hatte der Beschwerdeführer ausserehelichen Geschlechtsverkehr. Entgegen der im vorinstanzlichen Verfahren geäusserten Ansicht des Beschwerdeführers entspricht es keineswegs überholten Moralvorstellungen, hierin einen Widerspruch zu den herrschenden Ansichten über eine intakte eheliche Lebensgemeinschaft zu sehen. Von dem Seitensprung und der Schwangerschaft erfuhr die Ehefrau gemäss ihrer Aussage vom 10. November 2003 kurz vor der Scheidung. Die Frage, ob sich zwischen der Einbürgerung und dem gemeinsamen Scheidungsbegehren etwas Unvorhersehbares ereignet habe, das den Ehewillen abrupt und unwiederbringlich zerstört habe, verneinte sie. Vor diesem Hintergrund kann nicht davon ausgegangen werden, dass es sich bei der Verschlimmerung der ehelichen Probleme im Frühling 1999 um einen schlichten Zufall handelte. Vielmehr ist anzunehmen, dass die Ehe auf Grund längerer Belastung im Zeitpunkt der Einbürgerung nicht mehr intakt war und dass dies dem Beschwerdeführer bewusst war. Dass die Eheprobleme auf psychische Probleme der Ehegatten zurückzuführen sein sollen, steht dem nicht entgegen. Die weiteren vom Beschwerdeführer vorgebrachten Umstände vermögen an dieser Einschätzung nichts zu ändern. Insbesondere ist der Hinweis auf die Aussagen der Schwester seiner ehemaligen Frau und der gemeinsamen Hausärztin unbehelflich. Beide äusserten sich positiv über den Beschwerdeführer, erwähnten jedoch auch "Probleme in ihrer Beziehung" bzw. "längere Eheschwierigkeiten".
2.3.3 Aus den dargelegten Gründen ist davon auszugehen, dass der Beschwerdeführer im Verfahren der erleichterten Einbürgerung bewusst wahrheitswidrig bestätigt hat, in einer stabilen ehelichen Gemeinschaft zu leben. Die Vorinstanz hat deshalb zu Recht festgestellt, dass die Einbürgerung im Sinne von <ref-law> durch falsche Angaben oder Verheimlichung erheblicher Tatsachen erschlichen worden sei.
2.3.4 Damit ist auch der in diesem Zusammenhang vorgebrachte Eventualantrag abzuweisen, die Angelegenheit sei zur nochmaligen umfassenden Abklärung des Sachverhalts an die Vorinstanz zurückzuweisen. Zur Begründung führt der Beschwerdeführer verschiedene Aussagen an, welche seiner Ansicht nach ungenügend gewürdigt worden seien. Mit dieser Argumentation bemängelt er nicht die Feststellung des Sachverhalts durch die Vorinstanz, sondern deren Beweiswürdigung. Aus den vorangehenden Erwägungen ergibt sich, dass diese nicht zu beanstanden ist.
3. Der Beschwerdeführer bringt vor, die Nichtigerklärung der erleichterten Einbürgerung wäre unverhältnismässig. Seit ihm das Schweizer Bürgerrecht verliehen worden sei, seien neuneinhalb Jahre vergangen. Er sei vollständig integriert, so dass die Nichtigerklärung einer Entwurzelung gleichkäme. Dies umso mehr, als er als ehemaliger Bürger von Serbien, der aus dem Kosovo stamme, nun staatenlos wäre. Die rechtliche Stellung des Kosovo sei unklar, ebenso, wie und in welchem Staat er die Staatsbürgerschaft beantragen sollte.
Im Urteil 5A.18/2003 vom 19. November 2003 (in: ZBl 105/2004 S. 454) stellte das Bundesgericht fest, dass der direkte Adressat der Nichtigerklärung einer erleichterten Einbürgerung eine allfällige Staatenlosigkeit hinzunehmen habe. Für seine Familienmitglieder, die an der Erschleichung unbeteiligt seien, müsse die drohende Staatenlosigkeit zwar die Ausnahme sein. Für ihn selbst jedoch, der den Verlust des Schweizer Bürgerrechts zu verantworten habe, treffe dies nicht zu. Andernfalls wären potentiell Staatenlose vor einer Nichtigerklärung absolut geschützt (E. 3.3).
Von dieser Rechtsprechung abzuweichen, besteht kein Grund, mag sich auch die persönliche Verantwortlichkeit des Beschwerdeführers für die Nichtigerklärung im hier zu beurteilenden Fall von jener im zitierten teilweise unterscheiden. Inwiefern der Umstand, dass Kosovo bisher nur von einem Teil der Staatengemeinschaft anerkannt worden ist, eine Rolle spielt und wo der Beschwerdeführer eine Staatsbürgerschaft zu beantragen hätte, kann offen bleiben. Weder die angeblich drohende Staatenlosigkeit noch die geltend gemachte Entwurzelung führen zur Unverhältnismässigkeit der Nichtigerklärung (<ref-law>). Wie es sich mit einer allenfalls drohenden Staatenlosigkeit der Kinder des Beschwerdeführers verhält, ist aus den vorne in E. 1.2 genannten Gründen im vorliegenden Urteil nicht zu prüfen.
4. Der Beschwerdeführer macht weiter geltend, es sei die lange Dauer des Beschwerdeverfahrens vor der Vorinstanz sowie der Umstand zu berücksichtigen, dass die Nichtigerklärung der erleichterten Einbürgerung kurz vor Ablauf der Fünfjahresfrist von <ref-law> erfolgt sei. Zum jetzigen Zeitpunkt erfülle er die Voraussetzungen der ordentlichen Einbürgerung. Nach einer Nichtigerklärung der erleichterten Einbürgerung ein Verfahren um ordentliche Einbürgerung anzustrengen, sei prozessökonomisch nicht sinnvoll.
Die Auffassung des Beschwerdeführers, die Dauer des Beschwerdeverfahrens vor der Vorinstanz sei im Entscheid über die Nichtigerklärung zu berücksichtigen, geht fehl. Hat der Gesetzgeber eine Frist von fünf Jahren bestimmt, innert welcher das Bundesamt die Einbürgerung für nichtig erklären kann, so besteht diese Möglichkeit während der gesamten Frist. Eine Rechtsverzögerung wird vom Beschwerdeführer nicht geltend gemacht (vgl. <ref-law>).
Auch die Möglichkeit einer ordentlichen Einbürgerung nach <ref-law> steht der Nichtigerklärung einer erleichterten Einbürgerung nicht entgegen (Urteil 5A.18/2003 vom 19. November 2003, E. 2.3.2). Die ordentliche und die erleichterte Einbürgerung unterscheiden sich nicht nur in den inhaltlichen Voraussetzungen, sondern auch hinsichtlich der Zuständigkeit und des Verfahrens. Die Eigenheiten der ordentlichen Einbürgerung sind zu beachten und dürfen im Verfahren der Nichtigerklärung einer erleichterten Einbürgerung nicht umgangen werden.
5. Die Beschwerde ist nach dem Gesagten abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang trägt der Beschwerdeführer die Gerichtskosten (<ref-law>). Er hat keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Es wird keine Parteientschädigung zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, dem Bundesamt für Migration und dem Bundesverwaltungsgericht, Abteilung III, schriftlich mitgeteilt.
Lausanne, 18. November 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold