Sachverhalt: A. Am 26. Januar 2016 sprach A._ auf dem Betreibungsamt Seeland, Dienststelle Seeland, vor, um eine Betreibung gegen die B._ AG mit Sitz in U._ für eine Forderung von Fr. 100.-- einzuleiten. Der Dienststellenleiter verlangte von A._ einen Kostenvorschuss von Fr. 150.-- für die gewünschte Verrichtung. Er begründete den Kostenvorschuss mit dem Umstand, dass A._ als Schuldner beim Betreibungsamt verzeichnet sei. Dieser verliess das Betreibungsamt und reichte am 3. Februar 2016 Beschwerde beim Obergericht des Kantons Bern, Aufsichtsbehörde in Betreibungs- und Konkurssachen, ein. Mit Entscheid vom 29. Februar 2016 wies das Obergericht die Beschwerde ab. B. A._ ist mit Eingabe vom 3. März 2016 an das Bundesgericht gelangt. Der Beschwerdeführer beantragt die Aufhebung des angefochtenen Entscheides und die Rückweisung der Sache an die Vorinstanz. Das Obergericht hat unter Hinweis auf den angefochtenen Entscheid am 5. April 2016 auf eine Beschwerdeantwort verzichtet. Das Betreibungsamt hat sich nicht vernehmen lassen. Der Beschwerdeführer hat am 21. April 2016 repliziert.