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.

Erwägungen:
1.
1.1. Gegen Entscheide des Bundesverwaltungsgerichts über die Nichtigerklärung einer Einbürgerung steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> an das Bundesgericht offen. Streitgegenstand bildet hier einzig die Frage, ob das Bundesverwaltungsgericht ohne Verletzung von Bundesrecht auf die bei ihr eingereichte Beschwerde wegen Verspätung nicht eintreten durfte.
1.2. Der Beschwerdeführer war am vorinstanzlichen Verfahren beteiligt und ist als Betroffener der Nichtigerklärung seiner Einbürgerung sowie als direkter Adressat des angefochtenen Entscheids zur Beschwerde an das Bundesgericht legitimiert (vgl. <ref-law>).
1.3. Mit der Beschwerde an das Bundesgericht kann, von hier nicht interessierenden weiteren Möglichkeiten abgesehen, nur die Verletzung von Bundesrecht (vgl. <ref-law>) sowie die offensichtlich unrichtige Feststellung des Sachverhaltes (vgl. <ref-law>) gerügt werden.
1.4. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), prüft die bei ihm angefochtenen Entscheide aber grundsätzlich nur auf Rechtsverletzungen hin, die von den Beschwerdeführern geltend gemacht und begründet werden (vgl. <ref-law>). Gerügt wird hier einzig, ob das Bundesverwaltungsgericht ohne Rechtsverletzung von einer Einvernahme des angerufenen Zeugen für die angeblich am 16. Januar 2016 erfolgte Postaufgabe des vom Beschwerdeführer als Beschwerdeschrift bezeichneten Schreibens vom 15. Januar 2016 absehen durfte.
2.
2.1. Der Beschwerdeführer macht eine Gehörsverletzung geltend, weil das Bundesverwaltungsgericht die verlangte Befragung des von ihm angerufenen Zeugen verweigert hat. In diesem Zusammenhang rügt er ebenfalls ausdrücklich eine willkürliche Beweiswürdigung und zumindest sinngemäss offensichtlich unrichtige Sachverhaltsfeststellungen durch die Vorinstanz.
2.2. Die Parteien haben im verwaltungs- sowie im verwaltungsgerichtlichen Verfahren Anspruch auf rechtliches Gehör (<ref-law>). Dazu gehört, dass die Behörde alle erheblichen und rechtzeitigen Vorbringen der Parteien würdigt und die ihr angebotenen Beweise abnimmt, wenn diese zur Abklärung des Sachverhalts tauglich erscheinen. Umgekehrt folgt daraus, dass keine Verletzung des rechtlichen Gehörs vorliegt, wenn ein Gericht auf die Abnahme beantragter Beweismittel verzichtet, weil es auf Grund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener (antizipierter) Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 3.3 S. 64 mit Hinweis). Die Sachverhaltsfeststellung oder Beweiswürdigung einer Verwaltungs- oder Gerichtsbehörde ist (nur) dann als willkürlich zu bezeichnen (<ref-law>), wenn die Behörde den Sinn und die Tragweite eines Beweismittels offensichtlich verkannt hat, wenn sie ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn sie auf Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (vgl. <ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 4.2 S. 560).
2.3. Das Bundesverwaltungsgericht erwog, es sei nicht ersichtlich, dass der angerufene Zeuge aus eigener Wahrnehmung etwas zum Inhalt des angeblich rechtzeitig aufgegebenen Couverts aussagen könne. Weiter sei zu beachten, dass es sich, wie vom Beschwerdeführer selbst beschrieben, um einen langjährigen Freund handle. Zwischen der behaupteten Beobachtung vom 16. Januar 2016 und der eingereichten Bestätigung vom 14. April 2016 lägen drei Monate. Den im Brief enthaltenen Schilderungen liessen sich keine Besonderheiten entnehmen, die es plausibel machen könnten, weshalb dem Verfasser beispielsweise das genaue Datum noch präsent sei. Es sei nicht unwahrscheinlich, dass es sich um ein Gefälligkeitsschreiben handle, was in einer Gesamtbeurteilung zu berücksichtigen sei. Der Beschwerdeführer offeriere zwar als Beweis die Befragung des Freundes als Zeugen; im Verwaltungsverfahren seien Zeugenaussagen gegenüber anderen Beweismitteln aber subsidiär, und der Beschwerdeführer substantiiere seine Beweisofferte nicht. Angesichts der Zweifel an der schriftlichen Auskunft des Freundes sei der Beweisantrag abzuweisen. Überdies gebe es weitere Indizien, die gegen die Darstellung des Beschwerdeführers sprächen. So sei es seltsam, dass er sich während so langer Zeit nicht bei der Vorinstanz nach dem Verbleib seiner Beschwerde erkundigt habe, nachdem ihm keine Eingangsbestätigung zugegangen sei. Die eingereichte Kopie des Schreibens vom 15. Januar 2016 deute zudem auf eine Abänderung der Kopiervorlage hin. Im Übrigen sei unwahrscheinlich, dass der im Umgang mit Behörden nicht unerfahrene Beschwerdeführer eine so wichtige Eingabe nicht eingeschrieben verschickt hätte.
2.4. Das Bundesverwaltungsgericht hat ausführlich begründet, weshalb es auf eine Zeugenbefragung verzichtete. Die Begründung im angefochtenen Entscheid ist nachvollziehbar, und der Sachverhalt, von dem die Vorinstanz ausgegangen ist, steht mit den Akten nicht im Widerspruch und erscheint auch sonst nicht unhaltbar. Nach <ref-law> kann die Einvernahme von Zeugen angeordnet werden, wenn sich ein Sachverhalt auf andere Weise nicht hinreichend abklären lässt. Auf eine Zeugenbefragung darf insbesondere verzichtet werden, wenn willkürfrei davon ausgegangen werden kann, dass dadurch die durch andere Beweismittel erlangte Überzeugung der Behörde nicht geändert würde. Die Vorinstanz stützt ihre Einschätzung, der Beschwerdeführer vermöge seine Behauptung, am 16. Januar 2016 ein Beschwerdeschreiben in den Briefkasten der Hauptpost eingeworfen zu haben, auf mehrere einschlägige Anhaltspunkte. Auch wenn einzelne Gesichtspunkte für sich allein möglicherweise nicht genügen würden, um von einer Zeugenbefragung abzusehen, so ergeben doch alle bekannten und von der Vorinstanz abgewogenen Umstände zusammen ein Gesamtbild, das die Beweiswürdigung des Bundesverwaltungsgerichts stützt.
Vor Bundesgericht behauptet der Beschwerdeführer nunmehr, gerade weil er im Umgang mit Behörden erfahren sei, habe er seinen Freund gebeten, ihm als Zeuge für die Postaufgabe zu dienen. Wenn dies so wäre, dann erscheint aber umso weniger erklärbar, weshalb er sich nicht schon viel früher darauf berufen hat. So hätte er bereits zusammen mit der angeblichen Postaufgabe der Beschwerde eine Bestätigung des Zeugen einreichen oder diese sogar direkt auf dem Couvert anbringen lassen können. Dazu hätte er etwa anführen können, er sei mit dem Staatssekretariat fälschlicherweise davon ausgegangen, die Beschwerdefrist sei am 16. Januar 2016 und nicht, wie das Bundesverwaltungsgericht später erwogen hat, am 1. Februar 2016 abgelaufen, weshalb er von der Dringlichkeit der Postaufgabe ausgegangen sei. Insbesondere hätte er diesfalls aber seinen Zeugen spätestens mit Eingabe vom 22. März 2016, als er anwaltlich vertreten war, oder mit seinem selbst abgefassten Schreiben vom 6. April 2016 angerufen, nachdem er offenbar von der Mitteilung des Staatssekretariats vom 11. März 2016 erfahren hatte, die Nichtigerklärung sei rechtskräftig geworden. Da er seinen Freund angeblich gerade als Zeugen vorgesehen hatte, wäre es nichts als logisch gewesen, ihn gegenüber der Vorinstanz sofort anzurufen. Weshalb er das erst am 20. April 2016 nach Erhalt der Zwischenverfügung des Instruktionsrichters mit der Aufforderung, die Einhaltung der Beschwerdefrist zu beweisen, getan hat, ist unter diesen Umständen nicht erklärbar.
2.5. Das Bundesverwaltungsgericht durfte demnach in antizipierter Beweiswürdigung auf eine Zeugenbefragung verzichten. Weder sind die tatsächlichen Feststellungen der Vorinstanz offensichtlich unrichtig noch hat diese die Beweise willkürlich gewürdigt noch hat sie dem Beschwerdeführer das Gehör verweigert.
3.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen.
Bei diesem Verfahrensausgang wird der unterliegende Beschwerdeführer für das bundesgerichtliche Verfahren kostenpflichtig (Art. 66 Abs. 1, Art. 65 BGG). Eine Parteientschädigung ist nicht geschuldet (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird dem Beschwerdeführer, dem Staatssekretariat für Migration SEM und dem Bundesverwaltungsgericht, Abteilung VI, schriftlich mitgeteilt.
Lausanne, 24. November 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Uebersax