Sachverhalt:
A.
Die B._ AG liess A._ betreiben. Der Zahlungsbefehl in der Betreibung Nr. xxx wurde am 15. Oktober 2015 in Abwesenheit des Schuldners an C._ übergeben. Den vom Schuldner am 28. Oktober 2015 erhobenen Rechtsvorschlag wies das Betreibungsamt Region Solothurn mit Verfügung vom 2. November 2015 als verspätet ab.
B.
A._ stellte mit Schreiben vom 20. November 2015 ein Gesuch um Wiederherstellung der Frist. Er machte geltend, er sei davon ausgegangen, die Frist betrage 10 Arbeitstage. Des Weiteren hielt er dafür, die Zustellbescheinigung der Postbotin und die Zustellung an C._ seien widerrechtlich. Mit Urteil vom 22. Dezember 2015 wies die Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn das Gesuch ab.
C.
Mit Beschwerde in Zivilsachen vom 21. Januar 2016 (Postaufgabe) ist A._ an das Bundesgericht gelangt. Der Beschwerdeführer verlangt sinngemäss die Feststellung, dass der Zahlungsbefehl nicht rechtsgenüglich zugestellt wurde, eventualiter die Rückweisung an die Aufsichtsbehörde.
Es sind die kantonalen Akten beigezogen, hingegen keine Vernehmlassungen eingeholt worden.

Erwägungen:
1.
1.1. Entscheide kantonaler Aufsichtsbehörden in Schuldbetreibungs- und Konkurssachen unterliegen unabhängig eines Streitwertes der Beschwerde in Zivilsachen (Art. 72 Abs. 2 lit. a, Art. 74 Abs. 2 lit. c BGG). Die Beschwerde ist fristgerecht erhoben worden (<ref-law>) und - unter dem Vorbehalt einer rechtsgenüglichen Begründung - grundsätzlich zulässig.
1.2. Mit Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (<ref-law>; vgl. für Ausnahmen Abs. 2 dieser Norm) und prüft mit freier Kognition, ob der angefochtene Entscheid Recht verletzt. Es befasst sich aber nur mit formell ausreichend begründeten Rügen (<ref-law>; <ref-ruling> E. 1.1 S. 104 f.). In der Begründung ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Allgemein gehaltene Einwände, die ohne aufgezeigten oder erkennbaren Zusammenhang mit bestimmten Entscheidungsgründen vorgebracht werden, genügen nicht (<ref-ruling> E. 1.3 S. 584 mit Hinweisen).
1.3. Der vorinstanzlich festgestellte Sachverhalt ist für das Bundesgericht grundsätzlich verbindlich (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn die Feststellung offensichtlich unrichtig - d.h. willkürlich (<ref-ruling> E. 1.5 S. 130 mit Hinweis) - ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und die Behebung des Mangels für den Verfahrensausgang entscheidend sein kann (<ref-law>). Will der Beschwerdeführer die Sachverhaltsfeststellungen der Vorinstanz anfechten, muss er darlegen, inwiefern die genannten Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 4.2 S. 234; <ref-ruling> E. 5.1 S. 356). Bei der Rüge der offensichtlich unrichtigen Sachverhaltsfeststellung gilt das strenge Rügeprinzip (<ref-law>; <ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 5.1 S. 356).
1.4. Mit der Beschwerde in Zivilsachen darf der Beschwerdeführer keine neuen Tatsachen und Beweismittel vorbringen, es sei denn, erst der Entscheid der Vorinstanz habe dazu Anlass gegeben (<ref-law>). Diese Voraussetzung ist von vornherein nicht erfüllt, soweit eine Tatsache sich zwar auf das vorinstanzliche Prozessthema bezieht, jedoch erst nach dem Zeitpunkt eingetreten ist, in welchem sie im vorinstanzlichen Verfahren letztmals hätte berücksichtigt werden können. Solch "echte" Noven sind im bundesgerichtlichen Verfahren unzulässig. Gleiches gilt auch für Beweismittel, die erst nach dem angefochtenen Entscheid erstellt wurden (<ref-ruling> E. 3.1.2. S. 123; <ref-ruling> E. 5.2.4 S. 229; <ref-ruling> E. 2.1 S. 343 f.). Das vom Beschwerdeführer eingereichte Schreiben von C._ datiert vom 19. Januar 2016 und ist daher unbeachtlich.
2.
Von vornherein unzulässig ist die Beschwerde, soweit der Beschwerdeführer den materiellen Bestand der Betreibungsforderung sowie seine Schuldnereigenschaft bestreitet, weil diese Frage nicht Gegenstand des Verfahrens vor dem Betreibungsamt und der Aufsichtsbehörde bilden konnte und auch nicht Gegenstand des bundesgerichtlichen Verfahrens sein kann.
3.
Strittig ist nur mehr die Rechtsgültigkeit der Zustellung des Zahlungsbefehls. Der Beschwerdeführer macht sinngemäss geltend, dass mit der Zustellung an C._, die Regeln über die Zustellung von Betreibungsurkunden (<ref-law>) verletzt worden seien.
3.1. Die Betreibungsurkunden - vorliegend der Zahlungsbefehl (<ref-ruling> E. 3b S. 9) - werden dem Schuldner in seiner Wohnung oder an dem Orte, wo er seinen Beruf auszuüben pflegt, zugestellt. Wird er daselbst nicht angetroffen, so kann die Zustellung an eine zu seiner Haushaltung gehörende erwachsene Person oder an einen Angestellten geschehen (<ref-law>). Es kann, muss sich aber bei der betreffenden Person nicht um ein Familienmitglied handeln. Vorausgesetzt wird allerdings in beiden Fällen, dass sie im gleichen Haushalt wie der Schuldner wohnt (Urteil 5A_777/2011 vom 7. Februar 2012 E. 3.2.1).
Gemäss <ref-law> geschieht die Zustellung des Zahlungsbefehls durch den Betreibungsbeamten, einen Angestellten des Amtes oder durch die Post. Bei der Abgabe hat der Überbringer auf beiden Ausfertigungen zu bescheinigen, an welchem Tage und an wen die Zustellung erfolgt ist.
3.2. Vorliegend steht fest und ist unbestritten, dass der Zahlungsbefehl am 15. Oktober 2015 an C._ übergeben worden ist. Sodann ist die Vorinstanz offenbar davon ausgegangen und hat festgestellt, dass zwischen C._ und dem Beschwerdeführer kein blosses Untermietverhältnis besteht, - welches zur Annahme einer gemeinsamen Haushaltung im Sinne von <ref-law> nicht genügen würde (vgl. Urteil 5A_777/2011 vom 7. Februar 2012 E. 3.2.1 mit Hinweis auf JEANNERET/LEMBO, in: Commentaire romand, Poursuite et faillite, 2005, N. 24 zu <ref-law>) - sondern die Betroffenen vielmehr zusammen leben und daher von C._ eine unverzügliche Weiterleitung des Zahlungsbefehls an den eigentlichen Adressaten erwartet werden durfte. Diese Tatsachenfeststellung ist für das Bundesgericht verbindlich (vgl. E. 1.3), denn der Beschwerdeführer zeigt in keiner Weise auf, dass diese Feststellung willkürlich ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht. Namentlich legt er nicht dar, dass die Aufsichtsbehörde diesbezüglich tatsächlich erhebliche Vorbringen übergangen hat. Dies ist im Übrigen auch nicht ersichtlich, hat sich der Beschwerdeführer zur Stellungnahme des Betreibungsamts, in welcher dieses eine Integration des Beschwerdeführers in den Haushalt von C._ geltend gemacht hatte, im vorinstanzlichen Verfahren doch gar nicht geäussert. Soweit der Beschwerdeführer erstmals vor Bundesgericht behauptet, er sei bei C._ lediglich "Gast", setzter sich in unzulässiger Weise über die vorinstanzlichen Sachverhaltsfeststellungen hinweg. Da der vom Beschwerdeführer behauptete abweichende Sachverhalt mithin nicht berücksichtigt werden kann, ist auf die allein darauf gestützte Rüge der Verletzung von <ref-law> nicht einzutreten.
3.3. Der Beschwerdeführer macht weiter geltend, es handle sich bei der Zustellbescheinigung auf dem Zahlungsbefehl um ein "Falsifikat", da dieses Dokument von der Empfängerin selber gar nicht unterzeichnet worden sei.
Die Rüge ist offensichtlich unbegründet. Auf dem strittigen Zahlungsbefehl befindet sich die Bescheinigung des Überbringers, wonach die besagte Urkunde am 15. Oktober 2015 an C._ zugestellt wurde. Entgegen den Vorbringen des Beschwerdeführers liegt mithin ein den gesetzlichen Erfordernissen von <ref-law> entsprechendes Zustellzeugnis vor. Eine zusätzliche Bestätigung der Zustellung des Zahlungsbefehls durch Unterschrift des Empfängers bzw. der Empfängerin ist nicht erforderlich. Dass C._ das Schuldnerexemplar des Zahlungsbefehls auch effektiv übergeben wurde, wird vom Beschwerdeführer vor Bundesgericht im Übrigen auch nicht mehr bestritten.
4.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Das nachträgliche Gesuch um unentgeltliche Rechtspflege ist in Anwendung von <ref-law> abzuweisen, weil die Beschwerde von Anfang an aussichtslos erschien.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird dem Beschwerdeführer, dem Betreibungsamt Region Solothurn und der Aufsichtsbehörde für Schuldbetreibung und Konkurs des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 15. März 2016
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Buss