Faits:
A. A._, ressortissant kosovar né le 15 février 1978, est entré en Suisse le 28 février 1997 et y a déposé une demande d'asile. Par décision du 24 novembre 1997, l'Office fédéral des réfugiés (actuellement l'Office fédéral des migrations; ci-après: l'Office fédéral) a rejeté sa requête et prononcé son renvoi de Suisse. Le recours formé contre cette décision a été déclaré irrecevable le 28 avril 1998 par la Commission suisse de recours en matière d'asile. Le 27 mai 1999, l'intéressé a été mis au bénéfice de l'admission provisoire collective, conformément à l'arrêté du Conseil fédéral du 7 avril 1999. Cette mesure collective a été levée par décision du Conseil fédéral du 16 août 1999.
Le 14 janvier 2000, A._ a contracté mariage avec B._, ressortissante suisse née le 5 mars 1979. Il a de ce fait été mis au bénéfice d'une autorisation de séjour afin de pouvoir vivre auprès de son épouse. Aucun enfant n'est issu de cette union.
Le 3 février 2003, l'intéressé a déposé une demande de naturalisation facilitée. Dans le cadre de l'instruction de cette demande, le requérant et son épouse ont contresigné, le 2 septembre 2003, une déclaration écrite aux termes de laquelle ils confirmaient vivre en communauté conjugale effective et stable, résider à la même adresse et n'envisager ni séparation, ni divorce. Par décision du 7 octobre 2003, l'Office fédéral a accordé la naturalisation requise.
Le 29 mai 2007, les époux A._ et B._ ont introduit une requête commune de divorce et la dissolution de leur mariage a été prononcée par jugement du 11 octobre 2007.
B. Le 9 mai 2008, l'Office fédéral a informé A._ qu'il envisageait d'ouvrir une procédure visant à l'annulation de sa naturalisation facilitée, compte tenu notamment du fait que, selon les informations transmises par les autorités cantonales, les époux A._ et B._ avaient vécu séparés depuis 2004 et le divorce avait été prononcé sans qu'il n'y ait eu reprise de la vie commune.
Dans ses observations du 23 mai 2008, A._ a indiqué qu'il avait fait connaissance de sa future épouse en 1997 et qu'ils avaient vécu ensemble à partir de la mi-1998. La vie conjugale s'était fort bien déroulée pendant plusieurs années, les premières difficultés étant survenues à la fin 2004. Ils s'étaient séparés le 16 décembre 2004 mais avaient continué à se voir régulièrement et à entretenir des relations intimes jusqu'au début de l'année 2007. Ne désirant pas "chicaner son épouse", l'intéressé s'était rallié à la volonté de celle-ci de divorcer. Il leur était arrivé ce qui arrive à beaucoup de couples, "à savoir que tout à coup une désunion s'installe et que l'un des deux souhaite se séparer".
Le 16 juin 2008, B._ a répondu par écrit à un questionnaire sur les circonstances de sa rencontre et de son mariage avec l'intéressé, ainsi que sur sa vie conjugale et les raisons de sa séparation et de son divorce. A._ a contesté la teneur de certaines réponses de son ex-épouse. Il a notamment réaffirmé que les premières difficultés du couple étaient survenues à la fin de l'année 2004 et non en 2002 comme l'indiquait celle-ci. Il a également souligné que leur séparation était due à des raisons financières et à l'éloignement de son épouse pour motif de formation à l'école hôtelière à Thoune. Il a encore produit trois déclarations écrites de tiers à l'appui de ses propos.
Par décision du 25 septembre 2008, l'Office fédéral a prononcé, avec l'assentiment des autorités cantonales compétentes, l'annulation de la naturalisation facilitée accordée à A._.
Le 23 janvier 2009, l'intéressé a contracté mariage avec une ressortissante serbe, titulaire d'une autorisation d'établissement dans le canton de Neuchâtel, avec laquelle il faisait ménage commun depuis le mois d'avril 2007 selon le registre de contrôle des habitants de la ville de Neuchâtel.
C. Par arrêt du 25 novembre 2009, le Tribunal administratif fédéral a rejeté le recours de l'intéressé contre la décision précitée. Il a considéré en substance que l'examen des faits pertinents de la cause, ainsi que leur déroulement chronologique, amenaient à la conclusion que l'intéressé avait obtenu la naturalisation facilitée de manière frauduleuse. Celui-ci n'avait par ailleurs pas rendu vraisemblable la survenance d'un événement extraordinaire susceptible d'expliquer la détérioration du lien conjugal.
D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler l'arrêt du Tribunal administratif fédéral du 25 novembre 2009 et de dire qu'il y a lieu de maintenir la naturalisation facilitée qui lui a été accordée le 7 octobre 2003. Subsidiairement, il conclut au renvoi de la cause au Tribunal administratif fédéral pour nouvelle décision dans le sens des considérants. Il dit se plaindre d'un établissement inexact des faits et d'une violation du droit fédéral.
Le Tribunal administratif fédéral ainsi que l'Office fédéral ont renoncé à se déterminer.
Par ordonnance du 19 janvier 2010, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif présentée par le recourant.

Considérant en droit:
1. L'arrêt attaqué, qui émane du Tribunal administratif fédéral et concerne l'annulation de la naturalisation facilitée accordée au recourant, peut faire l'objet d'un recours en matière de droit public (art. 82 let. a et 86 al. 1 let. a LTF). Le motif d'exclusion de l'<ref-law> n'entre pas en ligne de compte, dès lors qu'il s'agit en l'espèce de naturalisation facilitée et non pas de naturalisation ordinaire. Pour le surplus, le recourant possède la qualité pour recourir au sens de l'<ref-law> et les conditions formelles de recevabilité sont remplies, de sorte qu'il y a lieu d'entrer en matière.
2. Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Quant au recourant, il ne peut critiquer la constatation de faits, susceptibles d'avoir une influence déterminante sur l'issue de la procédure, que si ceux-ci ont été établis de manière manifestement inexacte ou en violation du droit au sens de l'<ref-law>, en particulier en violation de l'interdiction constitutionnelle de l'arbitraire (<ref-law>; <ref-ruling> consid. 4.3 p. 62; Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, FF 2001 p. 4135).
Au début de son écriture, le recourant indique que son recours est notamment formé pour établissement inexact des faits au sens de l'<ref-law>. Il ne dit toutefois pas quels faits retenus dans l'arrêt attaqué seraient erronés, ni quels éléments déterminants le Tribunal administratif fédéral aurait éventuellement oublié de mentionner. Dans ces conditions, le Tribunal fédéral est lié par les faits établis par l'autorité précédente conformément à l'<ref-law>. Au demeurant, il apparaît que le recourant critique plutôt l'appréciation juridique des faits et soulève ainsi une question de droit que le Tribunal fédéral examine en l'espèce librement (cf. <ref-law>).
3. Conformément aux art. 41 al. 1 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (LN; RS 141.0) et 14 al. 1 de l'ordonnance du 17 novembre 1999 sur l'organisation du Département fédéral de justice et police (RS 172.213.1), l'Office fédéral des migrations peut, avec l'assentiment de l'autorité du canton d'origine, annuler dans les cinq ans une naturalisation facilitée obtenue par des déclarations mensongères ou par la dissimulation de faits essentiels.
3.1 Pour qu'une naturalisation facilitée soit annulée, il ne suffit donc pas qu'elle ait été accordée alors que l'une ou l'autre de ses conditions n'était pas remplie; il faut qu'elle ait été acquise grâce à un comportement déloyal et trompeur. S'il n'est pas besoin que ce comportement soit constitutif d'une escroquerie au sens du droit pénal, il est nécessaire que l'intéressé ait donné sciemment de fausses informations à l'autorité ou qu'il l'ait délibérément laissée dans l'erreur sur des faits qu'il savait essentiels (<ref-ruling> consid. 3.1 p. 115 et les arrêts cités). Tel est notamment le cas si le requérant déclare vivre en communauté stable avec son conjoint alors qu'il envisage de se séparer une fois obtenue la naturalisation facilitée; peu importe que son mariage se soit ou non déroulé jusqu'ici de manière harmonieuse (arrêt 5A.22/2006 du 13 juillet 2006 consid. 2.2).
La nature potestative de l'art. 41 al. 1 LN confère une certaine liberté d'appréciation à l'autorité compétente, qui doit toutefois s'abstenir de tout abus dans l'exercice de celle-ci. Commet un abus de son pouvoir d'appréciation l'autorité qui se fonde sur des critères inappropriés, ne tient pas compte de circonstances pertinentes ou rend une décision arbitraire, contraire au but de la loi ou au principe de la proportionnalité (<ref-ruling> consid. 3.1 p. 115; <ref-ruling> consid. 4a p. 101 et les arrêts cités).
3.2 La procédure administrative fédérale est régie par le principe de la libre appréciation des preuves (art. 40 de la loi fédérale de procédure civile fédérale du 4 décembre 1947 [PCF; RS 273], applicable par renvoi de l'art. 19 de la loi fédérale du 20 décembre 1968 sur la procédure administrative [PA; RS 172.021]). Ce principe vaut également devant le Tribunal administratif fédéral (<ref-law>). L'administration supporte le fardeau de la preuve lorsque la décision intervient, comme en l'espèce, au détriment de l'administré. Cela étant, la jurisprudence admet dans certaines circonstances que l'autorité puisse se fonder sur une présomption. C'est notamment le cas pour établir que le conjoint naturalisé a menti lorsqu'il a déclaré former une union stable, dans la mesure où il s'agit d'un fait psychique, lié à des éléments relevant de la sphère intime, souvent inconnus de l'administration et difficiles à prouver (<ref-ruling> consid. 3.2 p. 485). Partant, si l'enchaînement rapide des événements fonde la présomption de fait que la naturalisation a été obtenue frauduleusement, il incombe alors à l'administré, en raison non seulement de son devoir de collaborer à l'établissement des faits (<ref-law>; cf. <ref-ruling> consid. 3.2 p. 115 s.), mais encore dans son propre intérêt, de renverser cette présomption (<ref-ruling> consid. 3.2 p. 485 s.).
S'agissant d'une présomption de fait, qui ressortit à l'appréciation des preuves et ne modifie pas le fardeau de la preuve (cf. <ref-ruling> consid. 3.2 p. 486), l'administré n'a pas besoin, pour la renverser, de rapporter la preuve contraire du fait présumé, à savoir faire acquérir à l'autorité la certitude qu'il n'a pas menti; il suffit qu'il parvienne à faire admettre l'existence d'une possibilité raisonnable qu'il n'ait pas menti en déclarant former une communauté stable avec son conjoint. Il peut le faire en rendant vraisemblable, soit la survenance d'un événement extraordinaire susceptible d'expliquer une détérioration rapide du lien conjugal, soit l'absence de conscience de la gravité de ses problèmes de couple au moment de la signature de la déclaration commune (<ref-ruling> consid. 3 p. 165 s.; arrêt 5A.12/2006 du 23 août 2006 consid. 2.3 et les arrêts cités).
4. 4.1 En l'espèce, le Tribunal administratif fédéral a estimé que l'enchaînement rapide des faits ainsi que le court laps de temps entre l'octroi de la naturalisation facilitée (7 octobre 2003) et la séparation du couple (fin 2004) était de nature à fonder la présomption que la naturalisation avait été obtenue de manière frauduleuse et que le couple n'envisageait déjà plus une vie future partagée lors de la signature de la déclaration de vie commune. Cette conviction était renforcée par plusieurs autres éléments, à savoir le statut précaire du recourant sur le plan administratif lors de son mariage, les premières difficultés conjugales apparues en 2002 ainsi que l'absence d'activités ou de loisirs communs.
Le recourant allègue que sa situation administrative avant le mariage n'était pas déterminante, puisqu'il faisait déjà ménage commun avec sa future épouse depuis plus d'une année et demie et qu'il n'avait pas d'informations sûres qu'il devait quitter la Suisse. Cette question peut rester indécise, puisqu'il n'est de toute façon pas contesté que les époux A._ et B._ se sont mariés dans le but premier de fonder une communauté conjugale. Autre est la question de savoir si, au moment de la déclaration commune du 2 septembre 2003 et du prononcé de la naturalisation facilitée, le lien matrimonial était toujours stable et effectif. Le recourant maintient que tel était le cas, les premières difficultés n'étant survenues qu'à partir de la fin 2004. L'Office fédéral ainsi que le Tribunal administratif fédéral ont toutefois retenu que le couple était sujet à des difficultés bien avant la séparation de 2004, soit en tout cas dès que B._ a entrepris une formation à Thoune, et qu'à cet éloignement s'ajoutaient d'autres difficultés (notamment d'ordre financier et du fait de l'absence d'activités communes). L'intéressée a en effet affirmé que les problèmes conjugaux avaient commencé dès le début de sa formation à l'école hôtelière en 2002 et que même si, à l'époque, elle croyait que son mariage durerait toujours, la situation a rapidement changé lorsqu'elle a commencé ladite formation, au point que le couple s'était séparé à la fin de l'année 2004. Le recourant a aussi reconnu que la séparation avait été provoquée non seulement par des motifs financiers, mais aussi du fait que l'épouse était souvent éloignée en raison de sa formation, qui s'est étendue de 2002 à 2004. Dans son écriture, le recourant insiste toutefois sur le fait que son ex-épouse n'a jamais entrepris une quelconque procédure matrimoniale avant 2007; elle aurait même admis que ce n'est qu'à partir de septembre 2006 qu'il y aurait eu des discussions concrètes concernant une séparation, preuve que même si elle considérait qu'il y avait des difficultés conjugales avant cette date, celles-ci étaient certainement peu importantes. On peut cependant relever à cet égard que la formation de B._ à Thoune, et donc son éloignement, ont pris fin en 2004, ce qui n'a néanmoins pas permis aux époux de se rapprocher et de régler leurs différends. C'est au contraire à ce moment-là qu'ils ont pris la décision de se séparer et ils ne se sont plus remis ensemble jusqu'à la dissolution de leur mariage. Par ailleurs, en 2006, les conjoints étaient séparés depuis deux ans déjà et il est peu probable qu'ils envisageaient encore de reprendre la vie conjugale; il ressort en effet du dossier que B._ a rencontré son futur époux en 2006 et que le recourant s'est mis en ménage avec sa future épouse en avril 2007. C'est donc en vain que le recourant soutient que la requête de divorce, déposée seulement en mai 2007, serait une preuve, ou à tout le moins une présomption, qu'auparavant le lien conjugal n'était pas détruit et qu'une possibilité de reprise de la vie commune existait toujours. S'agissant des vacances communes, le recourant allègue qu'il est allé avec son épouse à Appenzell, à Ascona et en Autriche durant leur vie commune et que le couple n'est pas parti dans son pays d'origine en raison de la guerre. Ceci n'empêche que les époux n'avaient pas d'activités ou de loisirs communs et que, à part les quelques occasions mentionnées par le recourant, ils ne partaient jamais en vacances ensemble et ne partageaient que rarement leur temps libre. Il résulte de ce qui précède que les éléments retenus par le Tribunal administratif fédéral sont propres à fonder la présomption que la naturalisation du recourant a été obtenue frauduleusement. Les déclarations écrites des tiers concernant l'harmonie du couple ne permettent pas d'affaiblir ladite présomption.
4.2 Selon la jurisprudence précitée, il incombait dès lors au recourant de renverser cette présomption en rendant vraisemblable, soit la survenance d'un événement extraordinaire, susceptible d'expliquer une dégradation aussi rapide du lien conjugal, soit l'absence de conscience de la gravité de ses problèmes de couple au moment de la signature de la déclaration commune.
Pour expliquer les motifs de la désunion, le recourant se contente d'alléguer que "ce qui leur était arrivé arrive à beaucoup de couples, à savoir que tout à coup une désunion s'installe et que l'un des deux souhaite se séparer". Il ne s'agit manifestement pas d'un événement extraordinaire, qui serait survenu de manière inattendue et subite, précisément une année après l'obtention de la nationalité suisse. Les éventuelles difficultés qui peuvent surgir entre époux, après plusieurs années de vie commune, dans une communauté de vie effective, intacte et stable, n'entraînent en effet la désunion, selon l'expérience générale, qu'au terme d'un processus prolongé de dégradation des rapports conjugaux, en principe entrecoupés de tentatives de réconciliation (cf. arrêt 5A.11/2006 du 27 juin 2006 consid. 4.1 et arrêt 5A.18/2003 du 19 novembre 2003 consid. 2.2). D'ailleurs, comme il a été relevé au considérant précédent, les difficultés conjugales sont apparues dès le début de la formation de B._ à l'école hôtelière en 2002, soit près d'une année et demie avant l'octroi de la naturalisation facilitée. Dans ces circonstances, il apparaît que le recourant n'a pas réussi à rendre vraisemblable la survenance d'un événement extraordinaire susceptible d'expliquer une dégradation aussi rapide du lien conjugal et que les éléments avancés ne permettent pas de renverser la présomption établie. En particulier, sa bonne intégration n'est pas pertinente pour déterminer si la naturalisation a été obtenue de façon frauduleuse ou non. Il en découle que les conditions d'application de l'art. 41 LN sont remplies et que le Tribunal administratif fédéral n'a pas abusé de son pouvoir d'appréciation en confirmant l'annulation de la naturalisation facilité octroyée au recourant.
5. Les considérants qui précèdent conduisent au rejet du recours. Le recourant, qui succombe, doit supporter les frais judiciaires (art. 65 et 66 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, fixés à 2'000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué au mandataire du recourant, à l'Office fédéral des migrations et au Tribunal administratif fédéral, Cour III.
Lausanne, le 24 février 2010
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: La Greffière:
Féraud Mabillard