Sachverhalt:
A.
B._ leitete mit Zahlungsbefehl vom 24. April 2019 des Betreibungsamtes Bern-Mittelland, Dienststelle Mittelland in der Betreibung Nr. xxx gegen A._, Inhaber der Einzelunternehmung A._ Bauunternehmung, für eine Forderung von insgesamt Fr. 884.25 zuzüglich Zins zu 5 % seit dem 27. Juni 2018 auf Fr. 649.25 die Betreibung ein. Der Zahlungsbefehl konnte A._ am 29. April 2019 zugestellt werden. Am 22. Mai 2019 stellte das Betreibungsamt A._ auf Begehren von B._ die Konkursandrohung zu.
B.
Am 29. Mai 2019 (Postaufgabe) erhob A._ gegen die Konkursandrohung beim Obergericht des Kantons Bern als Aufsichtsbehörde in Betreibungs- und Konkurssachen Beschwerde. Er beantragte, die Konkursandrohung sei aufzuheben, weil er Rechtsvorschlag erhoben habe. Mit Entscheid vom 20. August 2019 wies die Aufsichtsbehörde die Beschwerde ab.
C.
Mit Eingabe vom 2. September 2019 ist A._ an das Bundesgericht gelangt. Der Beschwerdeführer beantragt die Aufhebung des angefochtenen Entscheids und der Konkursandrohung.
Mit Verfügung vom 3. September 2019 wurde das Gesuch um aufschiebende Wirkung (mangels Begründung) abgewiesen.
Die Aufsichtsbehörde, das Betreibungsamt und der Gläubiger haben auf die Einreichung einer Vernehmlassung zur Beschwerde verzichtet.

Erwägungen:
1.
1.1. Angefochten ist ein Entscheid der einzigen kantonalen Aufsichtsbehörde, welcher die Konkursandrohung zum Gegenstand hat. Entscheide kantonaler Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen unterliegen unabhängig von einer gesetzlichen Streitwertgrenze der Beschwerde in Zivilsachen (<ref-law> i.V.m. <ref-law>, Art. 74 Abs. 2 lit. c und Art. 75 Abs. 1 BGG).
1.2. Der Beschwerdeführer, welchem die Fortsetzung der Betreibung auf dem Wege des Konkurses angedroht wurde, ist zur Beschwerde in Zivilsachen legitimiert (<ref-law>). Die Beschwerde ist fristgemäss erhoben worden (<ref-law>) und zulässig.
1.3. Mit der vorliegenden Beschwerde kann insbesondere die Verletzung von Bundesrecht gerügt werden (<ref-law>). In der Beschwerde ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>; <ref-ruling> E. 2). Die Verletzung verfassungsmässiger Rechte ist ebenfalls zu begründen, wobei hier das Rügeprinzip gilt (<ref-ruling> E. 2.4).
1.4. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Dabei bedeutet "offensichtlich unrichtig" willkürlich (<ref-ruling> E. 1.2.2).
2.
Anlass zur Beschwerde gibt die Frage, ob der Beschwerdeführer den Nachweis erbracht hat, gegenüber der zustellenden Postbotin unmittelbar bei der Zustellung des Zahlungsbefehls Rechtsvorschlag erhoben zu haben.
2.1. Die Vorinstanz hat es als erstellt erachtet, dass der Beschwerdeführer unmittelbar bei der Zustellung des Zahlungsbefehls keinen Rechtsvorschlag erhoben hat. Erst nach der Zustellung habe er die Postbotin C._ privat kontaktiert, um sie zu bitten, den Rechtsvorschlag auf dem Schuldnerdoppel zu erfassen, was diese in der Folge auch getan habe. Die Vorinstanz hat sich dabei neben dem Gläubigerdoppel des Zahlungsbefehls, auf welchem kein Rechtsvorschlag verurkundet wurde, massgeblich auf den Mailverkehr zwischen dem Betreibungsamt und der Schweizerischen Post vom 17./24. Juni 2019 gestützt.
2.2. Der Beschwerdeführer rügt namentlich eine willkürliche Beweiswürdigung. Er macht zusammengefasst geltend, er habe sehr wohl gleich bei der Zustellung gegenüber der Postbotin Rechtsvorschlag erhoben und sich dies schriftlich bestätigen lassen. Offensichtlich habe es die Postbotin versehentlich unterlassen, die Erhebung des Rechtsvorschlags auch auf dem Gläubigerdoppel zu notieren. Die Behauptung der Schweizerischen Post, wonach der Vermerk auf dem Schuldnerdoppel von der Postbotin erst später angebracht worden sei, habe er bereits im vorinstanzlichen Verfahren entschieden zurückgewiesen. Eine direkte Aussage der Postbotin dazu liege nicht vor. In den Akten befinde sich lediglich die E-Mail einer Postmitarbeiterin der Supportzentrale, welche sich auf "interne Abklärungen" beziehe. Zum Zeitpunkt, wann die handelnde Postbotin nachträglich dazu gedrängt worden sein soll, die Erhebung des Rechtsvorschlags auf dem Schuldnerdoppel zu bescheinigen, mache die Schweizerische Post keine Aussagen. Aufgrund der allgemeinen Lebenserfahrung müsse davon ausgegangen werden, dass ihm als Einzelunternehmer in der Baubranche die Grundzüge des Betreibungsverfahrens bekannt seien und ihm bewusst gewesen sei, dass, wenn er keinen Rechtsvorschlag erheben würde, ihm der Konkurs angedroht wird. Die Vorstellung, dass er die Postbotin nachträglich "gedrängt" (Aussage Schweizerische Post) bzw. "gebeten" (Feststellung der Vorinstanz im angefochtenen Entscheid) haben soll, eine Rechtsvorschlagsbescheinigung mit falschem Datum auszustellen und die Postbotin auch noch darauf eingegangen sei, sei lebensfremd. Unhaltbar und damit willkürlich sei auch, dass die Vorinstanz die Postbotin zu diesem aussergewöhnlichen Vorgang nicht einmal persönlich befragt habe.
2.3.
2.3.1. Der Zahlungsbefehl wird jeweils im Doppel ausgefertigt. Ein Exemplar ist für den Betriebenen und das andere für den Betreibenden bestimmt (<ref-law>). Die Zustellung des Zahlungsbefehls geschieht durch den Betreibungsbeamten, einen Angestellten des Amts oder durch die Post (<ref-law>). Bei der Abgabe hat der Überbringer auf beiden Ausfertigungen zu bescheinigen, an welchem Tag und an wen die Zustellung erfolgt ist (<ref-law>).
Will der Betriebene Rechtsvorschlag erheben, so hat er dies sofort dem Überbringer des Zahlungsbefehls oder innert zehn Tagen nach der Zustellung dem Betreibungsamt mündlich oder schriftlich zu erklären (<ref-law>). Dem Überbringer, insbesondere dem Postboten gegenüber, kann der Rechtsvorschlag solange abgegeben werden, als die Zustellung andauert. Nach beendigter Zustellung kann der Rechtsvorschlag nicht mehr gegenüber einem Postboten oder Beamten erklärt werden (<ref-ruling> E. 2; BESSENICH, in: Basler Kommentar, Bundesgesetz über Schuldbetreibung und Konkurs, 2. Aufl. 2010, N. 9 zu <ref-law>; RUEDIN, in: Commentaire romand, Poursuite et faillite, 2005, N. 4 zu <ref-law>). Auf diese Rechtslage wird auf dem Zahlungsbefehl gut ersichtlich hingewiesen.
Bei einem mündlichen Rechtsvorschlag hat die zustellende Person diesen sogleich auf beiden Doppeln des Zahlungsbefehls zu bescheinigen (AMONN/WALTHER, Grundriss des Schuldbetreibungs- und Konkursrechts, 9. Aufl. 2013, § 18 Rz. 12). Falls der Rechtsvorschlag von der zustellenden Person einzig auf dem Schuldnerdoppel vermerkt wurde, gilt er grundsätzlich als erhoben, denn bei Abweichungen zwischen dem Schuldnerexemplar und demjenigen des Gläubigers ist bei der Fortsetzung der Betreibung die dem Schuldner zugestellte Ausfertigung massgebend (<ref-law>). Dabei liegt es beim Schuldner, sich bei der mündlichen Erklärung des Rechtsvorschlags der Protokollierung zu versichern (BGE 32 I 761 S. 769; WÜTHRICH/SCHOCH, in: Basler Kommentar, Bundesgesetz über Schuldbetreibung und Konkurs, 2. Aufl. 2010, N. 13 zu <ref-law>; vgl. auch <ref-law>). Schliesslich kann die irrtümliche Angabe auf dem Gläubigerdoppel, der Schuldner habe keinen Rechtsvorschlag erhoben, nicht nur durch das Schuldnerdoppel, sondern auch durch andere Beweismittel widerlegt werden (BGE 26 I 239 S. 240; WÜTHRICH/SCHOCH, a.a.O., N. 10 zu <ref-law>; s. zum Ganzen auch die Stellungnahme des Bundesgerichts vom 8. Januar 2004 zur Anfrage der Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt, in: BlSchK 2004 S. 92).
2.3.2. Gemäss <ref-law> stellt die Aufsichtsbehörde den Sachverhalt von Amtes wegen fest. Die am Verfahren Beteiligten trifft eine Mitwirkungspflicht dahingehend, dass sie die Aufsichtsbehörde bei der Sachverhaltsermittlung nach bestem Wissen und Gewissen zu unterstützen haben. Der in <ref-law> festgehaltene Untersuchungsgrundsatz verlangt von der Aufsichtsbehörde, das Verfahren zu leiten, die relevanten Tatsachen und erforderlichen Beweismittel zu bestimmen, die Beweiserbringung anzuordnen und die erhobenen Beweise von Amtes wegen zu würdigen. Soweit die richtige Gesetzesanwendung es erfordert, muss die Aufsichtsbehörde die relevanten Tatsachen selber ermitteln und darf nicht bloss abwarten, ob die Parteien Instruktionsmassnahmen verlangen oder ob sie von sich aus geeignete Beweise beibringen (Urteile 5A_253/2015 vom 9. Juni 2015 E. 4.1; 5A_9/2011 vom 28. März 2011 E. 4.3; 5A_902/2010 vom 28. Februar 2011 E. 2.1; LORANDI, Betreibungsrechtliche Beschwerde und Nichtigkeit, 2000, N. 55 zu <ref-law>). Wo zur Feststellung des Sachverhalts eine Beweiserhebung unumgänglich ist, sollen daher auch die Aufsichtsbehörden zu den prozessüblichen Beweismitteln - insbesondere Urkunden, Zeugen und Sachverständige - greifen; ihre Erhebungen haben sich aber in vernünftigem Rahmen zu bewegen und zu berücksichtigen, dass das Zwangsvollstreckungsverfahren speditiv abzuwickeln ist (<ref-ruling> E. 3; COMETTA/MÖCKLI, in: Basler Kommentar, Bundesgesetz über Schuldbetreibung und Konkurs, 2. Aufl. 2010, N. 7 zu <ref-law>). Im Übrigen findet im betreibungsrechtlichen Beschwerdeverfahren <ref-law>, aus dem die Rechtsprechung einen bundesrechtlichen Anspruch auf Abnahme anerbotener Beweise ableitet (<ref-ruling> E. 2.6; <ref-ruling> E. 4a), analoge Anwendung (<ref-ruling> E. 1; GRONER, Beweisrecht, 2011, S. 55 f.).
2.3.3. Vorliegend steht fest, dass die Postbotin C._ auf dem Schuldnerdoppel des Zahlungsbefehls in der Betreibung Nr. xxx die Erhebung des Rechtsvorschlags durch den Beschwerdeführer unterschriftlich bescheinigt hat, wobei das von der zustellenden Postbotin notierte Datum unter der Rubrik Rechtsvorschlag mit demjenigen unter der Rubrik Zustellbescheinigung übereinstimmt. Nur wenn der vorinstanzlich festgestellte Sachverhalt (oben E. 2.1) zutreffen würde, d.h. die Bescheinigung des Rechtsvorschlags durch die Postbotin nicht formell korrekt zustandegekommen (weil die zustellende Postbotin erst zu einem späteren Zeitpunkt um Protokollierung des Rechtsvorschlags gebeten wurde und dazu gar nicht mehr zuständig war) und überdies auch inhaltlich unrichtig wäre (weil unmittelbar bei der Zustellung gegenüber der Überbringerin effektiv gar kein Rechtsvorschlag erhoben wurde), wäre die gültige Erhebung eines Rechtsvorschlags durch den Beschwerdeführer zu verneinen. Dem Bericht der Schweizerischen Post gemäss E-Mail vom 24. Juni 2019 hat der damals noch nicht anwaltlich vertretene Beschwerdeführer jedoch im kantonalen Verfahren vehement entgegnet, dass es sich um blosse Schutzbehauptungen handle, um Fehler nicht einzugestehen. Darin ist sinngemäss der Antrag zu erblicken, die betreffende Postbotin als Zeugin zu befragen. Im Beschwerdeverfahren nach Art. 17/18 SchKG dürfen rechtsprechungsgemäss nicht so strenge Anforderungen an das Anerbieten von Beweisen gestellt werden wie in einem Zivilprozess (<ref-ruling> E. 2; Urteil 5A_487/2009 vom 12. Oktober 2009 E. 3.3.1). Das muss insbesondere gelten, wenn es um die Frage der Erhebung des Rechtsvorschlags geht und die zustellende Person den Rechtsvorschlag überdies auf dem Schuldnerdoppel unterschriftlich als geschehen verurkundet hat. Indem die Vorinstanz von einer persönlichen Befragung abgesehen hat, hat sie <ref-law> verletzt. Dass ihre Überzeugung durch eine persönliche Befragung der Postbotin aller Voraussicht nach nicht geändert würde (sog. antizipierte Beweiswürdigung), durfte die Vorinstanz unter den gegebenen Umständen ohne Verletzung des Willkürverbots (<ref-law>) nicht annehmen. Zumal vorliegend ein eher ungewöhnlicher Geschehensablauf im Raum steht und die zeitlichen Verhältnisse etwas undurchsichtig geblieben sind, hätte sich eine persönliche Befragung der Postbotin aufgedrängt. Die Sache ist daher an die Vorinstanz zurückzuweisen, damit sie die Postbotin C._ als Zeugin befragt und anschliessend neu entscheidet.
3.
Die Rückweisung der Sache zu ergänzender Abklärung gilt für die Frage der Auferlegung der Gerichtskosten wie auch der Parteientschädigung als vollständiges Obsiegen, unabhängig davon, ob sie beantragt und ob das entsprechende Begehren im Haupt- oder im Eventualantrag gestellt wird (<ref-ruling> E. 11.1). Ungeachtet des Ausgangs des Verfahrens werden dem Kanton Bern keine Gerichtskosten auferlegt (<ref-law>); hingegen hat er den anwaltlich vertretenen Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Der Entscheid des Obergerichts des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, vom 20. August 2019 wird aufgehoben und die Sache an die Vorinstanz zu neuem Entscheid im Sinne der Erwägungen zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Bern hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'000.-- zu entschädigen.
4.
Dieses Urteil wird dem Beschwerdeführer, dem Betreibungsamt Bern-Mittelland, Dienststelle Mittelland, B._ und dem Obergericht des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, schriftlich mitgeteilt.
Lausanne, 10. Dezember 2019
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Buss