Sachverhalt: A. A.a Am 24. September 2010 liess das Betreibungsamt Zürich 11 die Zahlungsbefehle in den vom Staat A._ und von der Stadt A._ eingeleiteten Betreibungen Nrn. 1 und 2 im Schweizerischen Handelsamtsblatt und im Amtsblatt des Kantons Zürich publizieren, nachdem die persönlichen und polizeilichen Zustellversuche an X._ nicht erfolgreich waren. Es wurde kein Rechtsvorschlag erhoben. Die daraufhin ausgestellten Pfändungsankündigungen konnten dem Vertreter des Betriebenen am 25. November 2010 im Amtslokal des Betreibungsamtes ausgehändigt werden. A.b Am 30. November 2010 stellte X._ beim Bezirksgericht Zürich als unterer kantonaler Aufsichtsbehörde über Betreibungsämter das Gesuch, die Frist für den Rechtsvorschlag in den Betreibungen Nr. 1 und 2 wieder herzustellen. Die Eingabe wurde sinngemäss als Beschwerde gegen die Zustellung durch öffentliche Bekanntmachung der beiden Zahlungsbefehle, eventualiter als Gesuch um Wiederherstellung der jeweiligen Rechtsvorschlagsfristen entgegengenommen und mit Beschluss vom 30. März 2011 insgesamt abgewiesen. B. Hiergegen gelangte X._ am 5. Mai 2011 an das Obergericht des Kantons Zürich als obere kantonale Aufsichtsbehörde über Schuldbetreibung und Konkurs und erneuerte seinen vor dem Bezirksgericht erhobenen Antrag. Mit Beschluss vom 9. Juni 2011 trat das Obergericht auf die Beschwerde wegen Verspätung nicht ein. C. X._ ist mit Beschwerde vom 30. Juni 2011 und einer Ergänzung vom 19. Juli 2011 an das Bundesgericht gelangt. Der Beschwerdeführer beantragt die Aufhebung des Beschlusses der oberen kantonalen Aufsichtsbehörde und die Rückweisung der Sache zur Neubeurteilung an die Vorinstanz. Zudem begehrt er die Gewährung der aufschiebenden Wirkung, welchem Gesuch sich das Betreibungsamt sowie der Staat Zürich und die Stadt Zürich als Beschwerdegegner widersetzen. Mit Verfügung vom 5. September 2011 gewährte die Präsidentin der II. zivilrechtlichen Abteilung der Beschwerde antragsgemäss die aufschiebende Wirkung. In der Sache sind keine Vernehmlassungen eingeholt worden. Mit der Stellungnahme zum Gesuch um aufschiebende Wirkung haben sich das Betreibungsamt und die Beschwerdegegner unaufgefordert zur Beschwerde vernehmen lassen. 