Sachverhalt: A. X._ (geb. 1952) stammt aus der Türkei. Er war dort mit der türkischen Staatsangehörigen A._ (geb. 1955) verheiratet, mit der er vier gemeinsame Kinder (geb. 1980, 1981, 1986 und 1989) hat. Mitte April 1990 reiste X._ in die Schweiz ein. Sein Asylgesuch wurde vom zuständigen Bundesamt und danach von der Asylrekurskommission mit Urteil vom 16. August 1993 abgewiesen. Am 30. Oktober 1993 liess sich X._ von seiner Ehefrau in der Türkei scheiden. Am 26. November 1993 reichte er ein erstes Gesuch um Revision des Asylentscheids ein, welches von der Asylrekurskommission am 11. März 1994 abgewiesen wurde. Ein zweites Revisionsgesuch vom 18. Juli 1994 zog er am 24. Mai 1996 zurück. Kurz zuvor, am 18. Mai 1996, hatte er im Kanton Nidwalden die Schweizer Bürgerin Y._(geb. 1950) geheiratet. Aufgrund dieser Heirat wurde X._ eine Aufenthaltsbewilligung erteilt. B. Am 15. Juni 1999 ersuchte X._ um die erleichterte Einbürgerung. Im Rahmen des Einbürgerungsverfahrens unterzeichneten er und Y._ am 10. Juli 2000 gemeinsam eine Erklärung, wonach sie in einer tatsächlichen, ungetrennten und stabilen ehelichen Gemeinschaft an derselben Adresse zusammenlebten und weder Trennungs- noch Scheidungsabsichten hätten. Sie nahmen unterschriftlich zur Kenntnis, dass die erleichterte Einbürgerung nicht möglich ist, wenn vor oder während des Einbürgerungsverfahrens einer der Ehegatten die Trennung oder Scheidung beantragt hat oder keine tatsächliche eheliche Gemeinschaft mehr besteht. Ebenso bestätigten sie zu wissen, dass die Verheimlichung solcher Umstände zur Nichtigerklärung der Einbürgerung führen könne. Am 10. August 2000 wurde X._ erleichtert eingebürgert. Nebst dem Schweizer Bürgerrecht erwarb er die Bürgerrechte des Kantons Obwalden und der Gemeinde Lungern. C. Am 1. Februar 2001 meldete sich Y._ von der gemeinsamen Wohnadresse ab. Sie und X._ reichten am 14. September 2001 gemeinsam ein Scheidungsbegehren ein. Mit Urteil vom 27. März 2002 schied das Amtsgericht Hochdorf die Ehe. Am 16. März 2003 stellte X._ im Kanton Luzern ein Gesuch um Nachzug seiner beiden jüngsten Kinder aus seiner ersten Ehe. D. Vom Amt für Migration des Kantons Luzern auf die erwähnten Sachumstände aufmerksam gemacht, leitete das Bundesamt für Migration (BFM) am 22. April 2004 gegen X._ ein Verfahren betreffend Nichtigerklärung der erleichterten Einbürgerung ein. E. Am 14. Juni 2005 erteilte der Heimatkanton Obwalden die Zustimmung zur Nichtigerklärung der erleichterten Einbürgerung. Mit Verfügung vom 24. Juni 2005 erklärte das Bundesamt die erleichterte Einbürgerung von X._ als nichtig. F. X._ erhob am 26. Juli 2005 beim Eidgenössischen Justiz- und Polizeidepartement (EJPD) Beschwerde gegen die Verfügung des BFM vom 24. Juni 2005 und beantragte deren vollumfängliche Aufhebung. Sodann ersuchte er um Gewährung der unentgeltlichen Rechtspflege samt Verbeiständung sowohl im laufenden als auch im erstinstanzlichen Verfahren. Das Bundesverwaltungsgericht, welches die beim EJPD am 1. Januar 2007 hängigen Beschwerden übernahm, wies die Beschwerde mit Urteil vom 31. März 2009 bezüglich der Nichtigerklärung der erleichterten Einbürgerung ab (Dispositiv-Ziffer 1). Hinsichtlich der unentgeltlichen Rechtspflege im Verfahren vor dem Bundesamt hiess es die Beschwerde teilweise gut und änderte die Verfügung des BFM dahingehend, dass dem Gesuch um Bewilligung der unentgeltlichen Rechtspflege im erstinstanzlichen Verfahren teilweise entsprochen und auf die Erhebung einer Gebühr verzichtet werde. Soweit das Gesuch auf die Bestellung eines unentgeltlichen Rechtsbeistandes gerichtet sei, werde es abgewiesen (Dispositiv-Ziffer 2). Sodann verpflichtete das Bundesverwaltungsgericht die Vorinstanz, X._ für das Verfahren vor dem Bundesverwaltungsgericht eine Parteientschädigung von Fr. 500.-- auszurichten (Dispositiv-Ziffer 3) und entschädigte den unentgeltlichen Rechtsbeistand von X._ für das Rechtsmittelverfahren mit Fr. 2'000.-- (Dispositiv-Ziffer 4). G. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt X._, die Dispositiv-Ziffern 1 und 2 des Urteils des Bundesverwaltungsgerichts vom 31. März 2009 sowie die Verfügung des Bundesamtes für Migration vom 24. Juni 2005 seien aufzuheben. Es sei festzustellen, dass die Vorinstanzen in schwerwiegender Weise das Beschleunigungsgebot und das rechtliche Gehör verletzt hätten, was im Ergebnis zu einer Aufhebung der angefochtenen Verfügungen, eventualiter zu einer zusätzlichen Entschädigung nach Ermessen des Gerichts führe. Dem Beschwerdeführer sei im erstinstanzlichen Verfahren die unentgeltliche Rechtspflege zu erteilen. Im Verfahren vor Bundesgericht sei der Beschwerde die aufschiebende Wirkung zu gewähren und ebenfalls die unentgeltliche Rechtspflege und -verbeiständung zu bewilligen. H. Das Bundesverwaltungsgericht und das BFM verzichten auf eine Vernehmlassung in der Sache. I. Mit Präsidialverfügung vom 8. Juni 2009 wurde der Beschwerde im bundesgerichtlichen Verfahren die aufschiebende Wirkung zuerkannt.