Faits:
A. A._, ressortissant du Bengladesh né en 1968, est arrivé en Suisse en hiver 1991. Il y a déposé une demande d'asile, qui a été définitivement rejetée le 19 juin 1992. Le 15 mai 1995, il a épousé à Neuchâtel B._, ressortissante suisse née en 1955. Il s'est alors vu délivrer une autorisation de séjour dans le but de vivre auprès de son épouse. Aucun enfant n'est issu de cette union.
Le 7 août 2000, A._ a déposé une demande de naturalisation facilitée fondée sur son mariage avec B._. Dans le cadre de l'instruction de cette demande, les époux ont contresigné, le 15 septembre 2001, 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. La déclaration signée précisait en outre que "si cet état de fait est dissimulé", la naturalisation facilitée pouvait être annulée dans les cinq ans. Par décision du 4 octobre 2001, l'Office fédéral des étrangers (actuellement Office fédéral des migrations [ODM]) a accordé la naturalisation facilitée à A._.
B. Le 27 mars 2002, B._ a déposé une requête de mesures protectrices de l'union conjugale auprès du Président du Tribunal civil du district de Neuchâtel. Par ordonnance du 8 janvier 2004, cette autorité judiciaire a notamment pris acte de la volonté commune des époux de vivre séparés et du fait que A._ s'était constitué un domicile propre dès le 1er avril 2002. Le 9 novembre 2004, les époux ont déposé une requête commune tendant au prononcé de leur divorce. Le divorce des époux A._ et B._ a été prononcé le 18 avril 2005 par le Tribunal civil du district de Neuchâtel.
Le 28 décembre 2004, l'Office fédéral de l'immigration, de l'intégration et de l'émigration (IMES, devenu ensuite l'ODM) a fait savoir à A._ qu'il envisageait d'ouvrir une procédure en vue d'une éventuelle annulation de la naturalisation facilitée. L'intéressé a présenté des observations le 24 janvier, le 11 août et le 20 octobre 2005. Le 16 janvier 2006, l'ODM a interpellé l'avocate ayant représenté B._ au sujet des violences conjugales alléguées par celle-ci dans la procédure de divorce. Le 12 juin 2006, l'avocate en question a répondu qu'elle n'avait plus de contact avec sa cliente et que, "pour des raisons de langue", celle-ci ne comprenait absolument pas ses sollicitations. A._ n'a pas été informé de cet échange de correspondances. Par ailleurs, l'ODM lui a refusé la consultation de certaines pièces du dossier, en application de l'<ref-law>.
Par décision du 30 août 2006, l'ODM a prononcé l'annulation de la naturalisation facilitée de A._, avec l'assentiment des autorités compétentes du canton des Grisons. Cet office a considéré que le mariage de l'intéressé n'était pas constitutif d'une communauté conjugale effective et stable au moment de la signature de la déclaration commune du 15 septembre 2001 et de l'octroi de la naturalisation facilitée, de sorte que celle-ci avait été obtenue sur la base de déclarations mensongères et d'une dissimulation de faits essentiels. L'enchaînement rapide des événements - demande de naturalisation, mariage, obtention de la naturalisation facilitée, séparation et divorce - fondait la présomption que la naturalisation avait été obtenue frauduleusement, présomption que l'intéressé n'était pas parvenu à renverser.
C. A._ a recouru contre cette décision auprès du Département fédéral de justice et police. La cause a été transmise au Tribunal administratif fédéral, conformément à l'art. 53 al. 2 de la loi sur le Tribunal administratif fédéral (LTAF; RS 173.32). Par arrêt du 12 décembre 2008, le Tribunal administratif fédéral a rejeté ce recours. Il a constaté une violation du droit d'être entendu du recourant en relation avec le courrier de l'avocate de son ex-épouse daté du 16 juin 2006; ce vice de procédure avait toutefois été réparé devant le Tribunal administratif fédéral. Cette autorité a également estimé que l'ODM avait appliqué correctement les art. 27 et 28 PA s'agissant des pièces demeurées confidentielles. Enfin, Tribunal administratif fédéral a confirmé l'appréciation de l'ODM concernant la présomption que la naturalisation avait été obtenue frauduleusement, les éléments avancés par A._ n'étant pas suffisants pour renverser cette présomption.
D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler cet arrêt et de dire qu'il a droit au maintien de sa naturalisation facilitée. Subsidiairement, il requiert que l'affaire soit renvoyée à l'autorité inférieure pour que la violation de son droit d'être entendu soit réparée. Il se prévaut de l'art. 29 al. 2 Cst. et se plaint d'une constatation arbitraire des faits et d'une violation de l'art. 41 de la loi fédérale du 29 septembre 1952 sur l'acquisition et la perte de la nationalité suisse (LN; RS 141.0). L'ODM et le Tribunal administratif fédéral ont renoncé à se déterminer.

Considérant en droit:
1. L'arrêt entrepris émane du Tribunal administratif fédéral et concerne l'annulation de la naturalisation facilitée accordée au recourant, si bien qu'il peut faire l'objet d'un recours en matière de droit public devant la Cour de céans (art. 82 al. 1 let. a et 86 al. 1 let. a LTF, art. 29 al. 1 let. f RTF). 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 a 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. Dans un grief d'ordre formel qu'il convient d'examiner en premier lieu, le recourant invoque l'art. 29 al. 2 Cst. pour se plaindre d'une violation de son droit d'être entendu.
2.1 Tel qu'il est garanti à l'art. 29 al. 2 Cst., le droit d'être entendu comprend notamment le droit pour l'intéressé de s'exprimer sur les éléments pertinents avant qu'une décision ne soit prise touchant sa situation juridique, le droit de consulter le dossier, de produire des preuves pertinentes, d'obtenir qu'il soit donné suite à ses offres de preuve pertinentes, de participer à l'administration des preuves essentielles ou à tout le moins de s'exprimer sur son résultat, lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.2 p. 494, V 368 consid. 3.1 p. 371; <ref-ruling> consid. 2.2 p. 504 s.; <ref-ruling> consid. 2b p. 56; <ref-ruling> consid. 3a p. 51 et les arrêts cités). Par exception au principe de la nature formelle du droit d'être entendu, une violation de ce dernier est considérée comme réparée lorsque l'intéressé jouit de la possibilité de s'exprimer librement devant une autorité de recours disposant du même pouvoir d'examen que l'autorité inférieure, et qui peut ainsi contrôler librement l'état de fait et les considérations juridiques de la décision attaquée (<ref-ruling> consid. 2.2 p. 204; <ref-ruling> consid. 2.2.3 p. 135; <ref-ruling> consid. 3d/aa p. 437; <ref-ruling> consid. 2b p. 132).
2.2 En l'espèce, le recourant se plaint du fait qu'il n'a pas été informé de l'échange de correspondances entre l'ODM et l'avocate de son ex-épouse et qu'il n'a donc pas pu se déterminer sur la réponse du 12 juin 2006. Or, l'ODM aurait retenu un élément décisif sur la base de ce document, à savoir le fait que son ex-épouse n'avait pas compris le sens de la déclaration commune signée le 15 septembre 2001. Le Tribunal administratif fédéral a constaté une violation du droit d'être entendu à cet égard, mais il a considéré que ce vice de procédure avait été réparé. Le recourant ne remet pas sérieusement en question cette appréciation, mais il se borne à affirmer qu'elle est arbitraire, sans aucunement le démontrer. Cette critique est dès lors irrecevable. Au demeurant, l'intéressé a bien été en mesure de s'exprimer de manière complète et détaillée sur la question devant le Tribunal administratif fédéral, qui dispose d'un plein pouvoir d'examen (cf. art. 49 de la loi fédérale du 20 décembre 1968 sur la procédure administrative [PA; RS 172.021], applicable par renvoi de l'<ref-law>), de sorte que le vice est effectivement réparé.
Pour le surplus, le recourant se plaint du fait qu'il n'a pas pu requérir le témoignage de son ex-épouse au sujet de la déclaration commune du 15 septembre 2001. Compte tenu des éléments fondant la présomption d'une obtention frauduleuse de la naturalisation facilitée (cf. infra consid. 3.2), la question de savoir si l'ex-épouse du recourant avait bien compris la déclaration commune n'apparaît pas décisive, de sorte qu'il n'est pas établi que ce moyen de preuve ait été de nature à influer sur la décision litigieuse. Quoi qu'il en soit, le recourant n'allègue pas avoir formellement requis cette mesure d'instruction devant le Tribunal administratif fédéral, de sorte qu'on ne saurait voir une violation du droit d'être entendu à cet égard. Ce premier moyen doit donc être rejeté, dans la mesure où il est recevable.
3. Invoquant une violation de l'art. 41 LN, le recourant reproche en substance au Tribunal administratif fédéral d'avoir retenu à tort qu'il avait obtenu sa naturalisation facilitée de manière frauduleuse.
3.1 Conformément aux art. 41 al. 1 LN 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.1 Pour qu'une naturalisation facilitée soit annulée, il ne suffit pas qu'elle ait été obtenue 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 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 latitude à l'autorité. Dans l'exercice de cette liberté, celle-ci doit s'abstenir de tout abus; 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; <ref-ruling> consid. 2 p. 310 et les arrêts cités).
3.1.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'<ref-law>). 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 (arrêt 1C_190/2008 du 29 janvier 2009, consid. 3 destiné à la publication et les arrêts cités).
3.2 En l'espèce, le Tribunal administratif fédéral a considéré que l'enchaînement des événements - déclaration commune le 15 septembre 2001, naturalisation le 4 octobre 2001 et introduction d'une demande de mesures protectrices de l'union conjugale le 27 mars 2002 - fondait la présomption 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 présomption de fait n'est pas discutée en l'occurrence. Elle peut effectivement se fonder sur un enchaînement rapide des événements, la séparation du couple étant survenue moins de six mois après l'obtention de la naturalisation. Il convient donc de déterminer si le recourant a pu renverser cette présomption, notamment en rendant vraisemblable qu'il n'avait pas menti en déclarant former une communauté stable avec son épouse.
3.2.1 Le Tribunal administratif fédéral a estimé que les explications données par le recourant n'étaient pas de nature à renverser la présomption. Les retrouvailles entre son ex-épouse et les anciennes collègues de celle-ci n'avait pas pu subitement précipiter la fin de la vie de couple des intéressés, sauf à considérer que leur union était inconsistante, aucune preuve n'ayant au demeurant été apportée à ce sujet. Le fait que le couple avait dû se rendre à l'évidence qu'il n'aurait pas d'enfant n'était pas non plus décisif, cette issue étant d'emblée envisageable dès lors que l'ex-épouse de l'intéressé était âgée de quarante ans au moment du mariage. Enfin, le recourant n'était pas crédible lorsqu'il affirmait avoir été surpris par la demande de séparation déposée par son ex-épouse le 27 mars 2002, puisque le bail à loyer de l'appartement qu'il a loué lorsqu'il a quitté le domicile conjugal a débuté le 1er avril 2002 déjà.
3.2.2 Le recourant ne remet pas en cause cette appréciation de manière convaincante. Il se borne à affirmer, sans aucunement le démontrer, que "l'entente dans le couple était harmonieuse" au moment de la demande et de l'octroi de la naturalisation. Il répète en outre que l'ODM aurait dû procéder à l'audition de son ex-épouse, mais il n'explique pas quels éléments cette mesure d'instruction aurait permis d'établir. Par ailleurs, les critiques du recourant portant sur les accusations de violences conjugales ne sont pas pertinentes, dans la mesure où le Tribunal administratif fédéral ne s'est pas fondé sur cet élément, laissant la question indécise. Le recourant se plaint enfin d'une constatation arbitraire des faits en ce qui concerne les circonstances de la rupture. Il est vrai que certaines affirmations contenues dans l'arrêt attaqué sont discutables, notamment celles relatives à "l'expérience générale" en matière de "processus prolongé de dégradation des rapports conjugaux, en principe entrecoupé de tentatives de réconciliation". On peut en effet difficilement admettre l'établissement de telles règles générales dans ce domaine. Cet élément n'est cependant pas déterminant en l'espèce, vu l'enchaînement des événements fondant la présomption de fait et l'absence d'éléments probants susceptibles de la renverser.
4. Il s'ensuit que le recours doit être rejeté, dans la mesure de sa recevabilité. Le recourant, qui succombe, doit supporter les frais de la présente procédure (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté, dans la mesure où il est recevable.
2. Les frais judiciaires, arrêté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 14 mai 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Rittener