Sachverhalt: A. Am 12. Juli bzw. 26. August 2011 vollzog das Betreibungsamt Küsnacht-Zollikon-Zumikon je einen Arrestbefehl über Fr. 6'100.-- zuzüglich Mehrwertsteuer und Zinsen bzw. über Fr. 2'200.-- zuzüglich Zinsen für Forderungen der Z._ Ltd. gegen X._. Verarrestiert wurde der dem Betriebenen zustehende "Liquidationsanteil an der einfachen Gesellschaft" mit seiner Ehefrau als Mitgesellschafterin hinsichtlich der "im Gesamteigentum stehenden Stockwerkeigentumsanteilen" in A._. In den Arresturkunden wurde vermerkt, "dass angesichts des derzeit laufenden Ehescheidungsverfahrens eine Lösung der Problematik betreffend Verwertung des Anteils des Arrestschuldners am Gesellschaftsgut möglich ist". Am 3. April 2012 wurde in den daraufhin von der Z._ Ltd. eingeleiteten Betreibungen Nr. xxx und Nr. yyy im Beisein des Schuldners die Pfändung vorgenommen. B. Das Betreibungsamt meldete daraufhin (am 4. April 2012) beim zuständigen Grundbuch die Pfändung eines Anteils an Gemeinschaftsvermögen (gemäss Art. 130 GBV) an; gleichzeitig bat es um Mitteilung, "falls der Schuldner nicht mehr als Gesamteigentümer eingetragen sein sollte". Darauf erhielt es vom Grundbuchamt den Hinweis, dass der Schuldner kraft dem am 17. Januar 2012 rechtskräftig gewordenen Scheidungsurteil Alleineigentümer der Liegenschaften sei. In der Folge nahm das Betreibungsamt eine überarbeitete Anmeldung vor, welcher am 10. April 2012 mit Formular (VZG Nr. 2) zur Vormerkung einer Verfügungsbeschränkung im Grundbuch (Art. 15 Abs. 1 lit. c und Abs. 3 VZG) stattgegeben wurde. Dagegen erhob X._ am 16. April 2012 Beschwerde beim Bezirksgericht Meilen als unterer kantonaler Aufsichtsbehörde über die Betreibungsämter. Er verlangte, auf die Anmeldung der Verfügungsbeschränkung nicht einzutreten bzw. das Grundbuchamt anzuweisen, diese wieder zu löschen. Mit Urteil vom 19. Juli 2012 wurde die Beschwerde abgewiesen. X._ wandte sich daraufhin an das Obergericht des Kantons Zürich als obere kantonale Aufsichtsbehörde über Schuldbetreibung und Konkurs, welches seine Beschwerde am 3. September 2012 ebenfalls abwies. C. X._ ist mit Beschwerde in Zivilsachen bzw. subsidiärer Verfassungsbeschwerde vom 8. September 2012 an das Bundesgericht gelangt. Er verlangt die Aufhebung des Urteils der oberen kantonalen Aufsichtsbehörde, eventualiter die Rückweisung der Sache an die Vorinstanz zur Neubeurteilung. Die kantonale Aufsichtsbehörde hat auf eine Antwort verzichtet. Das Betreibungsamt schliesst auf Abweisung der Beschwerde; gleichzeitig hat es die Pfändungsurkunde vom 21. Januar 2013 (betreffend den Pfändungsvollzug vom 3. April 2012) eingereicht. Die Z._ Ltd. als Beschwerdegegnerin hat sich vernehmen lassen, ohne einen formellen Antrag zu stellen.