Sachverhalt:
A. X._ wurde 1978 geboren und ist Bürger von Bangladesch. Im Februar 2001 gelangte er in die Schweiz und ersuchte um Asyl. Am 27. Januar 2003 wurde sein Gesuch abgewiesen und ihm bis zum 24. März 2003 eine Frist zum Verlassen des Landes gesetzt. Noch vor Ablauf der Ausreisefrist, am 14. Februar 2003, heiratete er Y._, eine 1954 geborene Schweizer Bürgerin surinamischer Abstammung und Mutter eines Sohns aus einer früheren Ehe mit einem Schweizer Bürger. In der Folge erteilte das Amt für Migration des Kantons Luzern X._ eine Aufenthaltsbewilligung zum Verbleib bei seiner Schweizer Ehefrau.
Am 11. Juni 2006 beantragte X._ die erleichterte Einbürgerung nach Art. 27 des Bundesgesetzes vom 29. September 1952 über Erwerb und Verlust des Schweizer Bürgerrechts (BüG; SR 141.0). Das Bundesamt für Migration (BFM) ersuchte daraufhin das Amt für Gemeinden des Kantons Luzern, um die Erstellung eines Erhebungsberichts. Dieser wurde am 31. Juli 2006 verfasst. Ungefähr ein Jahr später ersuchte das BFM das Amt für Gemeinden, eine Ergänzung zu dem Erhebungsbericht für den Zeitraum ab Juli 2006 einzureichen. Dieser Ergänzungsbericht datiert vom 9. August 2007 (mit nachgereichter Begründung vom 12. Dezember 2007) und gibt in Bestätigung des Erhebungsberichts die Einschätzung des Verfassers wieder, wonach vom Verdacht einer Scheinehe auszugehen ist. Mit Verfügung vom 11. März 2009 wies das BFM das Gesuch um erleichterte Einbürgerung ab. Zur Begründung führte es an, die Situation von X._ unmittelbar vor der Heirat, der grosse Altersunterschied zwischen den Ehegatten und die im Verfahren getätigten Erhebungen liessen ernsthaft daran zweifeln, dass eine tatsächliche, ungetrennte und stabile eheliche Gemeinschaft bestehe. Die Zweifel könnten mit den eingegangenen Referenzauskünften nicht zerstreut werden.
Auf eine gegen die Verfügung des BFM gerichtete Beschwerde hin stellte das Bundesverwaltungsgericht mit Urteil vom 18. Oktober 2011 fest, dass das Verfahren nicht innert der verfassungsmässig gebotenen Frist abgeschlossen worden sei. Insofern hiess es die Beschwerde gut; im Übrigen wies es sie jedoch ab.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 21. November 2011 beantragt X._, das Urteil des Bundesverwaltungsgerichts sei insofern aufzuheben, als die Erteilung des Schweizer Bürgerrechts abgelehnt worden sei. Die erleichterte Einbürgerung sei ihm zu gewähren. Zudem sei festzustellen, dass das Bundesverwaltungsgericht das Beschleunigungsgebot und das rechtliche Gehör verletzt habe.
Das Bundesverwaltungsgericht hat auf eine Vernehmlassung verzichtet. Das BFM schliesst auf Abweisung der Beschwerde. In der Folge liess sich der Beschwerdeführer unaufgefordert ein weiteres Mal vernehmen.

Erwägungen:
1. Das angefochtene Urteil, ein Endentscheid des Bundesverwaltungsgerichts (Art. 86 Abs. 1 lit. a, Art. 90 BGG), betrifft die Verweigerung der erleichterten Einbürgerung gestützt auf <ref-law>, somit eine öffentlich-rechtliche Angelegenheit im Sinne von <ref-law>. Die Ausnahme der ordentlichen Einbürgerung gemäss <ref-law> erstreckt sich nicht auf die erleichterte Einbürgerung. Der Beschwerdeführer hat sich am Verfahren vor der Vorinstanz beteiligt und ist beschwerdelegitimiert (<ref-law>). Auf die Beschwerde ist im Grundsatz einzutreten.
2. Noch bevor er auf den angefochtenen Entscheid eingeht, listet der Beschwerdeführer eine Reihe von Rechtsnormen auf, die er als verletzt erachtet. Darauf ist nur insoweit einzugehen, als der Beschwerdeführer im Nachgang dazu erläutert, weshalb diese Bestimmungen verletzt worden sein sollen. Im Übrigen ist darauf nicht einzutreten (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG). Dies gilt insbesondere für die Rüge, die Vorinstanz habe <ref-law> (SR 172.021) zu den Beschwerdegründen im Beschwerdeverfahren missachtet. Der Beschwerdeführer macht nicht geltend, das Bundesverwaltungsgericht habe seine Kognition rechtswidrig ausgedehnt oder eingeschränkt.
3. 3.1 Der Beschwerdeführer kritisiert, der angefochtene Entscheid sistiere das Verfahren, bis die kantonalen Behörden über die ausstehende ausländerrechtliche Bewilligung entschieden hätten. Dies stelle eine Rechtsverweigerung und eine Verletzung von Art. 6 und 13 EMRK dar.
3.2 Es trifft nicht zu, dass das Bundesverwaltungsgericht das Verfahren sistiert hat. Zwar hielt es in der Urteilsbegründung fest, in Konstellationen wie der vorliegenden rechtfertige es sich, das Verfahren um erleichterte Einbürgerung bis zur Klärung des ausländerrechtlichen Status des Gesuchsstellers auszusetzen oder aber, wenn auf einem Entscheid beharrt werde, die erleichterte Einbürgerung vorderhand zu verweigern. In der Folge erwog es jedoch auch, dass nicht zu beanstanden sei, dass das BFM die Voraussetzungen einer erleichterten Einbürgerung verneint habe. Die Beschwerde wies es deshalb ab. Eine Sistierung liegt somit nicht vor und die Rüge der Rechtsverweigerung ist unbegründet. Die Formulierung, die Einbürgerung sei "vorderhand" zu verweigern, ist offensichtlich so zu verstehen, dass nicht ausgeschlossen sei, dass eine spätere erneute Prüfung bei geänderter Aktenlage zu einer Gutheissung des Gesuchs führen könnte.
4. 4.1 Der Beschwerdeführer rügt, es sei willkürlich, den Vorwurf einer Scheinehe zu erheben. Bezeichnenderweise sei das BFM nie von einer Scheinehe ausgegangen. Es habe stets betont, es liege nur keine ausreichend stabile eheliche Gemeinschaft vor. Dass weder eine Scheinehe vorliege noch auch nur von einer nicht ausreichend stabilen ehelichen Gemeinschaft gesprochen werden könne, sei erwiesen. Aus den Akten sei ersichtlich, dass das Migrationsamt des Kantons Luzern die Aufenthaltsbewilligung über Jahre hinweg regelmässig verlängert habe, obwohl ihm die Heirat vor der Ausweisung und der Altersunterschied bekannt gewesen sei. Auch habe die Ehefrau bestätigt, dass die Ehe stabil sei. Die Ehe dauere mittlerweile 8 Jahre und 8 Monate. Auch von Drittpersonen seien keine Hinweise eingegangen, welche das eheliche Zusammenleben als Ganzes in Frage stellen würden. Die Vorinstanz weigere sich, auf die von ihm vorgelegten Referenzauskünfte abzustellen. Im Ergebnis laufe dies auf ein Beweisverbot hinaus, sei rechtsverweigernd und willkürlich.
4.2 Gemäss <ref-law> kann ein Ausländer nach der Eheschliessung mit einem Schweizer Bürger 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 dem Schweizer Bürger lebt. Das Bundesgericht geht davon aus, dass eine eheliche Gemeinschaft im Sinne von <ref-law> nicht nur das formelle Bestehen einer Ehe, sondern eine tatsächliche Lebensgemeinschaft voraussetzt. Eine solche Gemeinschaft kann nur bejaht werden, wenn der gemeinsame Wille zu einer stabilen 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 (<ref-ruling> E. 2 S. 164 f. mit Hinweisen).
In verfahrensrechtlicher Hinsicht richtet sich die erleichterte Einbürgerung nach den Bestimmungen des Verwaltungsverfahrensgesetzes. Danach gilt der Untersuchungsgrundsatz, wonach die Behörde den Sachverhalt von Amtes wegen festzustellen hat (<ref-law>). Mithin ist von der Behörde zu untersuchen, ob die Ehe im massgeblichen Zeitpunkt der Gesuchseinreichung und des Entscheids über die Einbürgerung tatsächlich gelebt wurde. Da es dabei im Wesentlichen um innere Vorgänge geht, die der Verwaltung oft nicht bekannt und schwierig zu beweisen sind, darf sie von bekannten Tatsachen (Vermutungsbasis) auf unbekannte (Vermutungsfolge) schliessen. Es handelt sich dabei um Wahrscheinlichkeitsfolgerungen, die aufgrund der Lebenserfahrung gezogen werden. Der Betroffene ist bei der Sachverhaltsabklärung mitwirkungspflichtig (<ref-ruling> E. 3 S. 165 f. mit Hinweisen). Lässt sich nicht nachweisen, dass die Voraussetzungen von <ref-law> erfüllt sind, erfolgt keine Einbürgerung. Insofern trifft die Beweislast den Gesuchsteller (vgl. Urteil 5A.2/2005 vom 24. März 2005 E. 2, in: Pra 2006 Nr. 64 S. 455).
4.3 Das Bundesverwaltungsgericht legte dar, es stehe klar der Verdacht einer Scheinehe im Raum. Die belastenden Indizien seien gewichtig. Der Beschwerdeführer habe eine Ehe nach negativem Ausgang eines Asylverfahrens geschlossen und sich damit den weiteren Verbleib in der Schweiz gesichert. Zwischen den Ehegatten bestehe ein erheblicher Altersunterschied. Hinzu kämen Ungereimtheiten im Zusammenhang mit den Wohn- und Lebensverhältnissen, so insbesondere die folgenden: Der Beschwerdeführer übernachte ohne plausiblen Grund teilweise auswärts; im gemeinsamen Schlafzimmer seien keine oder nur wenige Männerkleider im Schrank; es gebe keine überzeugende Erklärung dafür, weshalb Mieter der gemeinsamen Wohnung die Ehefrau und deren Ex-Ehemann seien, dies obwohl der Beschwerdeführer im fraglichen Zeitraum, d.h. Juni 2004, erwerbstätig gewesen sei und somit aus finanzieller Sicht ohne Weiteres als Mieter in Betracht gekommen wäre; während Jahren habe es eine provisorische bzw. gar keine Beschriftung des Briefkastens und der Türklingel gegeben. Diese Ungereimtheiten liessen sich mit den teilweise erst im Beschwerdeverfahren abgegebenen Erklärungsversuchen nicht ohne Weiteres beseitigen. Auch die Referenzauskünfte könnten nicht vom Bestand einer ehelichen Gemeinschaft überzeugen, da sie alle von den Eheleuten nahestehenden Personen stammten. Deren Einvernahme als Zeugen dürfte zu keinen anderen Erkenntnissen führen.
4.4 Die Hinweise auf die Wohn- und Lebensverhältnisse stützen sich in erster Linie auf die bereits erwähnten beiden Berichte des Amts für Gemeinden des Kantons Luzern.
Gemäss dem Bericht vom 31. Juli 2006 sprachen am Samstag, dem 29. Juli 2006 um 11:10 Uhr zwei Polizisten am ehelichen Domizil in Kriens vor. Der Beschwerdeführer sei nicht zu Hause gewesen. im Kleiderschrank des angeblich gemeinsamen Schlafzimmers hätten sich keine Herrenkleider befunden. Die Ehefrau habe dazu erklärt, dass der Beschwerdeführer nicht viele Kleider besitze. Seine Abwesenheit habe sie damit begründet, dass er nachts arbeite und danach manchmal bei Kollegen schlafe. Am späten Nachmittag habe das Ehepaar dann gemeinsam beim Polizeiposten vorgesprochen. Sie seien mit dem Umstand konfrontiert worden, dass die Türklingel der Wohnung mit "Y._ und Z._" angeschrieben sei. Die Ehefrau erklärte, dass "Z." für ihren im gleichen Haushalt lebenden Sohn Z._ stehe. Der Beschwerdeführer selbst habe geäussert, er besitze tatsächlich nur wenige Kleider und die meisten seien wahrscheinlich gerade in der Waschmaschine. Bei seinem Kollegen in Luzern übernachte er nur selten (ca. einmal im Monat). Abschliessend verweist der Bericht auf einen Raport der Kantonspolizei Luzern vom 22. März 2004, wonach am 15. März 2004 in Reussbühl in einer Privatwohnung eine Kontrolle durchgeführt und dabei nebst andern auch der Beschwerdeführer angetroffen worden sei. Dabei habe dieser den Beamten erklärt, dass er bei seiner Ehefrau in Horw wohne und in Reussbühl lediglich zu Besuch sei. Zum Umstand, dass in einem Kleiderschrank zwei Taschen mit diversen Bankunterlagen und seinem Reisepass gefunden worden seien, habe sich der Beschwerdeführer nicht äussern können. Alle vier in der Wohnung anwesenden Ausländer aus Bangladesch hätten sich kurz nach ihrer Einreise in die Schweiz mit Schweizer Bürgerinnen verheiratet, wobei in einem Fall die Ehefrau zugegeben habe, nur gegen Geld geheiratet zu haben.
Aus dem Ergänzungsbericht vom 9. August bzw. 12. Dezember 2007 geht hervor, dass die Kantonspolizei Luzern am 2. und 9. August 2007 erneut die eheliche Wohnung aufsuchte. Am Donnerstag, 2. August 2007, hätten um 18:50 Uhr zwei Polizisten vorgesprochen. Sie hätten mehrmals läuten müssen und während der Wartezeit Flüster- und andere Geräusche vernommen. Die Wohnung sei ihnen schliesslich durch die Ehefrau des Beschwerdeführers geöffnet worden. Bei ihr habe sich ein Mann aufgehalten, wobei sich die beiden als Kollegen bezeichnet hätten. Der Beschwerdeführer selbst habe sich zu jener Zeit bei der Arbeit befunden. Eine Woche später, am 9. August 2007 um 12:20 Uhr, seien der Beschwerdeführer, seine Ehefrau und deren Sohn angetroffen worden. Der Beschwerdeführer habe einige der an ihn gerichteten Fragen nicht sofort beantworten können und bei seiner Ehefrau nachfragen müssen. So habe er sich beispielsweise im Datum seiner Heirat ziemlich verschätzt.
4.5 Der Beschwerdeführer versucht, die von der Vorinstanz angeführten Ungereimtheiten zu erklären. Er übernachte manchmal, das heisse ca. einmal pro Monat bei einem Kollegen, weil er nachts arbeite. Dass am 26. Juli 2006 nur wenige Männerkleider im gemeinsamen Schlafzimmer gefunden worden seien, sei darauf zurückzuführen, dass er seine Sachen in einem Schrank im separaten Bad aufbewahre. In Bezug auf die am 2. August 2008 von der Polizei in der ehelichen Wohnung angetroffene Person weist er darauf hin, dass es sich dabei um einen Freund der Familie handle. Die Wohnung hätten seine Ehefrau und ihr Ex-Gatte gemietet, weil alle Beteiligten davon ausgegangen seien, dass die Chancen auf eine Wohnung grösser seien, wenn der Vertrag ausschliesslich auf die Schweizer Beteiligten laute. Sein Name habe deshalb auch nicht auf dem Briefkasten und der Türklingel gestanden, was nun jedoch schon seit längerer Zeit anders sei. Der Beschwerdeführer verweist schliesslich auf ein Protokoll einer Befragung durch das kantonale Amt für Migration vom 7. November 2008, woraus hervorgehen soll, weshalb er am 15. März 2004 in einer Privatwohnung in Reussbühl mit Pass und Bankunterlagen angetroffen worden ist. Mit diesem Protokoll lasse sich auch der Vorwurf der ungenügenden Kenntnisse der ehelichen Umstände und der Verhältnisse der Ehefrau vollständig entkräften.
4.6 Die Erklärungsversuche des Beschwerdeführers lassen verschiedene Fragen offen. So fällt auf, dass weder der Beschwerdeführer noch seine Ehefrau in ihren Angaben für den Bericht vom 31. Juli 2006 den separaten Schrank erwähnten, worin der Beschwerdeführer nach eigenen Angaben seine Kleider aufbewahrte. Auch die Erklärung für den am 15. März 2004 in Reussbühl von zwei Polizisten festgestellten Umstand, dass in einem Kleiderschrank zwei Taschen mit diversen Bankunterlagen und dem Reisepass des Beschwerdeführers lagen, lieferte er erst nachträglich, nämlich anlässlich der Befragung durch das kantonale Amt für Migration vom 7. November 2008 und mithin zu einem Zeitpunkt, als er bereits anwaltlich vertreten war. Aus dem Polizeirapport zur Personenkontrolle vom 15. März 2004 geht hervor, dass er vor Ort keine spontane Erklärung habe abgeben können. Der Beschwerdeführer irrt auch, wenn er annimmt, er habe bei der Befragung vom 7. November 2008 den Vorwurf der ungenügenden Kenntnisse der ehelichen Umstände und der Verhältnisse der Ehefrau vollständig entkräften können. Wesentlich erscheint diesbezüglich, dass der Beschwerdeführer noch am 9. August 2007, also etwa viereinhalb Jahre nach der Heirat, entsprechende Fragen nicht beantworten konnte. Ob er die Wissenslücken nachträglich schloss, ist weniger bedeutsam. Schliesslich vermag der Beschwerdeführer auch nicht plausibel zu erklären, weshalb sein Name nicht auf der Türklingel und dem Briefkasten stand. Dass die von der Liegenschaftsverwaltung gelieferten Schilder seinen Namen nicht enthielten, ist verständlich, doch leuchtet nicht ein, weshalb er diesen nicht wenigstens behelfsmässig angebracht hat.
Das Bundesverwaltungsgericht hat die Beweise nicht willkürlich gewürdigt, wenn es aufgrund des zeitlichen Zusammenhangs zwischen der Eheschliessung und dem abgelehnten Asylgesuch, dem grossen Altersunterschied und den genannten Ungereimtheiten bezüglich der Wohn- und Lebensverhältnisse der Ehegatten zum Schluss kam, es bestehe keine tatsächliche Lebensgemeinschaft gemäss <ref-law>. Wie bereits erwähnt, muss eine derartige Lebensgemeinschaft sowohl im Zeitpunkt der Gesuchseinreichung als auch im Zeitpunkt des Einbürgerungsentscheids bestehen. Dass das Bundesverwaltungsgericht in diesem Zusammenhang von einer eigentlichen Scheinehe spricht, ist im Übrigen unter dem Gesichtspunkt von <ref-law> nicht weiter relevant. Auf die Kritik des Beschwerdeführers an dieser Bezeichnung ist deshalb nicht weiter einzugehen. Die Vorinstanz hat auch kein Bundesrecht verletzt, wenn sie den vom Beschwerdeführer beigebrachten Referenzauskünften kein entscheidendes Gewicht beimass und die übrigen Beweise als zuverlässiger bewertete. Vor diesem Hintergrund durfte das Bundesverwaltungsgericht schliesslich willkürfrei davon ausgehen, dass die Anhörung der Referenzpersonen als Zeugen an seiner Überzeugung nichts ändern würde. Eine Verletzung des rechtlichen Gehörs (<ref-law>) liegt nicht vor (vgl. <ref-ruling> E. 5.3 S. 236 f.; <ref-ruling> E. 5.2 f. S. 147 f.; je mit Hinweisen).
Zusammenfassend ist festzuhalten, dass der Vorinstanz weder eine willkürliche Beweiswürdigung (<ref-law> i.V.m. <ref-law>) noch eine Verletzung von <ref-law> oder von <ref-law> vorzuwerfen ist. Die betreffenden Rügen sind unbegründet.
5. 5.1 Der Beschwerdeführer rügt, die Dauer des Verfahrens vor Bundesverwaltungsgericht sei zu lang gewesen, nachdem bereits das bisherige Verfahren sehr lange gedauert habe und zumal das Bundesverwaltungsgericht abgesehen von der Edition der Verfahrensakten keine Beweismassnahmen angeordnet habe.
5.2 Das Bundesverwaltungsgericht erwog, das Verfahren von der Einreichung des Einbürgerungsgesuchs bis zum Erlass seines eigenen Urteils habe mehr als fünf Jahre gedauert, und stellte eine Verletzung des Anspruchs auf Beurteilung innert angemessener Frist fest (<ref-law>). Die Verletzung hielt es im Dispositiv fest und berücksichtigte sie bei den Kosten- und Entschädigungsfolgen.
Das Bundesverwaltungsgericht hat somit in seinem Entscheid die gesamte bisherige Verfahrensdauer berücksichtigt, also auch jene Zeit, während der das Verfahren bei ihm selbst hängig war. Mit der Feststellung im Dispositiv und der Berücksichtigung bei den Kosten- und Entschädigungsfolgen hat es der Verletzung des Anspruchs auf Beurteilung innert angemessener Frist hinreichend Rechnung getragen und damit <ref-law> korrekt angewendet. Der angefochtene Entscheid verletzt diese Verfassungsbestimmung nicht. Die Rüge des Beschwerdeführers ist unbegründet.
6. Die Beschwerde ist 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, 21. Februar 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Dold