Sachverhalt: A. Am 4. September 2012 wurde A._ erleichtert eingebürgert. Am 16. Dezember 2015 eröffnete das Staatssekretariat für Migration SEM (nachfolgend: Staatssekretariat) A._ seine Verfügung vom 14. Dezember 2016, mit der es die erleichterte Einbürgerung nichtig erklärte. Nachdem gegen diesen Entscheid keine Beschwerde beim Bundesverwaltungsgericht eingegangen war, teilte das Staatssekretariat der zuständigen kantonalen Behörde mit, die Nichtigerklärung sei rechtskräftig geworden. B. B.a. Mit Eingaben vom 22. März und 6. April 2016 an das Bundesverwaltungsgericht machte A._ geltend, mit in Kopie eingereichtem Schreiben vom 15. Januar 2016 an das Bundesverwaltungsgericht rechtzeitig Beschwerde gegen die Verfügung über die Nichtigerklärung erhoben zu haben. In der Folge forderte ihn der Instruktionsrichter des Bundesverwaltungsgerichts auf, die Einhaltung der Beschwerdefrist zu beweisen. Am 20. April 2016 reichte A._ dem Bundesverwaltungsgericht ein von B._ unterzeichnetes Schreiben vom 14. April 2016 ein, in dem dieser als "langjähriger Freund" bestätigte, am 16. Januar mit A._ unterwegs gewesen zu sein, als dieser den Brief an das Bundesverwaltungsgericht in den Briefkasten am Hauptbahnhof Zürich eingeworfen habe. B.b. Mit Urteil vom 29. Juli 2016 trat das Bundesverwaltungsgericht auf die Beschwerde nicht ein. Es führte dazu im Wesentlichen aus, die Bestätigung des angerufenen Zeugen sei aus verschiedenen Gründen unglaubwürdig; es rechtfertige sich nicht, ihn mündlich anzuhören. C. Mit Beschwerde vom 5. September 2016 an das Bundesgericht beantragt A._, das Urteil des Bundesverwaltungsgerichts aufzuheben und dieses anzuweisen, die Befragung von B._ als Zeugen durchzuführen. Das Staatssekretariat schliesst ohne weitere Ausführungen auf Abweisung der Beschwerde. Das Bundesverwaltungsgericht verzichtete auf eine Stellungnahme.