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 (<ref-law>) 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.

Erwägungen:
1. 1.1 Entscheide kantonaler Aufsichtsbehörden über Verfügungen der Vollstreckungsorgane gemäss <ref-law> unterliegen der Beschwerde in Zivilsachen (<ref-law> i.V.m. <ref-law>). Sie ist unabhängig von einer gesetzlichen Streitwertgrenze gegeben (<ref-law>). Die Beschwerde ist fristgerecht erhoben worden (<ref-law>) und grundsätzlich zulässig. Damit entfällt die Verfassungsbeschwerde (<ref-law>).
1.2 Mit vorliegender Beschwerde kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>).
2. Anlass zur vorliegenden Beschwerde gibt vorerst der Wohnsitz des Beschwerdeführers.
2.1 Nach Auffassung der oberen Aufsichtsbehörde befindet sich der Wohnsitz des Beschwerdeführers nach wie vor in A._. Sie hat im Wesentlichen festgehalten, dass sich das Obergericht bereits mit Verfügung vom 8. Dezember 2011 eingehend mit der Wohnsitzfrage auseinandergesetzt habe und zum Schluss gekommen sei, dass die Vorbringen des Beschwerdeführers keine Annahme eines zwischenzeitlichen Wohnsitzwechsels zulasse. Damit könne insbesondere der Erstinstanz beigepflichtet werden, wenn diese festhalte, dass im vorliegenden Fall der ordentliche Betreibungsort und (aufgrund der sich dort befindenden Arrestgegenstände) auch der Arrestort in A._ sei. Die Vollstreckung gehe daher nicht nur in die verarrestierten Gegenstände, sondern in das ganze pfändbare Vermögen. Zudem sei die Anmeldung der Vormerkung einer Verfügungsbeschränkung im Grundbuch - mit Blick auf die ausführliche Begründung der Erstinstanz - nicht zu beanstanden.
2.2 Soweit der Beschwerdeführer "während der ganzen in Frage stehenden Zeitperiode" auf dem Wohnsitz in Tirana/Albanien besteht, kann ihm nicht gefolgt werden. Die diesbezüglichen Vorbringen des Beschwerdeführers erschöpfen sich in Behauptungen und Hinweisen auf verschiedene Gerichtsverfahren. Wo er sich mit der Absicht dauernden Verbleibens aufhält (vgl. <ref-law>, <ref-law>), richtet sich nach den objektiv erkennbaren Umständen und stellt ein Sachverhaltselement dar (vgl. <ref-ruling> E. 2a S. 8; Urteil 5A_270/2012 E. 4.2.3 vom 24. September 2012; BOLLIGER/ JEANNERET, in: Kurzkommentar SchKG, 2009, N. 3 zu <ref-law>), zu welchem sich die Vorinstanz verbindlich geäussert hat (<ref-law>). Den Begründungsanforderungen an eine Willkürrüge (<ref-law>) genügen die Behauptungen des Beschwerdeführers in keiner Weise (<ref-law>; <ref-ruling> E. 1.4.2 S. 254). Im Übrigen kommt dem Wohnort insoweit eine beschränkte Bedeutung zu, als er im konkreten Fall mit dem Arrestort zusammenfällt und sich die Pfändung auf die Arrestgegenstände beschränkt.
3. Alsdann wendet sich der Beschwerdeführer gegen den Vollzug der Pfändung, welche in zwei Betreibungen auf Prosequierung des Arrestes erfolgt ist.
3.1 Gemäss der vorinstanzlichen Feststellung fand die Pfändung am 3. April 2012 im Beisein des Schuldners statt. Das Betreibungsamt habe Grundstücke im Gesamteigentum "gemäss Arresturkunde" und damit einen Liquidationsanteil des Beschwerdeführers an einer einfachen Gesellschaft gepfändet, welche damals bereits liquidiert gewesen sei. Über die zwischenzeitlich erfolgte Liquidation habe der Beschwerdeführer entgegen seiner Auskunftspflicht nicht orientiert. Die vom Betreibungsamt vorgenommene Anmeldung zur Vormerkung der Verfügungsbeschränkung im Grundbuch sei nicht zu beanstanden.
3.2 Sinngemäss macht der Beschwerdeführer geltend, dass der verarrestierte Liquidationsanteil "im Rahmen der Scheidungsvereinbarung Null" betragen habe. Der Arrest sei daher dahingefallen, weshalb die Pfändung nicht in Frage komme. Dem Betreibungsamt stehe keine Kompetenz zu, anlässlich der Pfändung einen Ersatz für "eine verarrestierte wertlose oder untergegangene Sache" zu bestimmen. Darum wehre er sich gegen die Anmeldung der Vormerkung einer Verfügungsbeschränkung im Grundbuch.
3.3 Entgegen der Ansicht des Beschwerdeführers sind trotz Liquidation der Ehegatten-Gesellschaft pfändbare Vermögenswerte vorhanden. Sie sind weder untergegangen noch wertlos geworden, wie nachfolgend darzulegen ist. Gemäss Pfändungsprotokoll vom 3. April 2012 wurden Gegenstände "gemäss Arresturkunde" gepfändet, d.h. unbestrittenermassen der Liquidationsanteil des Beschwerdeführers an einer einfachen Gesellschaft. Mitgesellschafterin war seine Ehefrau. Die beiden Gesellschafter hielten zwei Stockwerkeigentumsanteile im Gesamteigentum. Ihre Ehe wurde bereits am 16. Dezember 2011 geschieden, welches Urteil am 17. Januar 2012 in Rechtskraft erwachsen ist. Damit gingen die beiden Stockwerkeigentumsanteile ins Alleineigentum des Beschwerdeführers über. Laut Pfändungsurkunde vom 21. Januar 2013 wurden entsprechend der vorangegangenen Verfügungsbeschränkung vom 10. April 2012 die im Alleineigentum stehenden Liegenschaften gepfändet.
3.4 Bei der Auflösung der Ehegatten-Gesellschaft sowie der Auflösung des Güterstandes (wegen Scheidung) sind zwei Phasen zu unterscheiden: Vorerst ist die einfache Gesellschaft zu liquidieren und dann das Liquidationsergebnis güterrechtlich zuzuordnen (HAUSHEER/ LINDENMAYER LIEB, Einfache Gesellschaft und Ehegüterrecht, in: Wolf [Hrsg.], Güter- und erbrechtliche Fragen zur einfachen Gesellschaft [...], 2005, S. 11). Wird in der ersten Phase der Anteil an einer Ehegatten-Gesellschaft verarrestiert bzw. gepfändet, so ist die Verordnung über die Pfändung und Verwertung von Anteilen an Gemeinschaftsvermögen (VVAG) zu beachten (GENNA, Auflösung und Liquidation der Ehegattengesellschaft, 2008, S. 71 ff.). Die Gläubiger können nur den Liquidationsanteil verarrestieren bzw. pfänden, nicht das Gesellschaftsvermögen (<ref-law>; <ref-law>). Nach der Verarrestierung bzw. Pfändung des Anteils können die Ehegatten lediglich die Auflösung der einfachen Gesellschaft beschliessen, oder es kann die Scheidung einen wichtigen Grund zur Auflösung der einfachen Gesellschaft darstellen (HAUSHEER/LINDENMAYER LIEB, a.a.O., S. 9). Für die Liquidation - wie für jede Verfügung über die zur Gemeinschaft gehörenden Vermögensgegenstände - bedarf es jedoch der Zustimmung des Betreibungsamtes (<ref-law>; Art. 96 Abs. 1, Art. 275 SchKG; FELLMANN/MÜLLER, Berner Kommentar, 2006, N. 232 u. 233 zu <ref-law>; BISANG, Die Zwangsverwertung von Anteilen an Gesamthandschaften, S. 119, 122, 137; GENNA, a.a.O., S. 73; vgl. betreffend Ehegatten-Gesellschaft Urteil 7B.184/2006 vom 6. Februar 2007 E. 3.2; vgl. betreffend die Erbengemeinschaft <ref-ruling> E. 2.2 S. 655 f.). Verfügungen, die ohne Bewilligung erfolgen, sind ungültig, wenn dadurch Rechte verletzt werden, die den Gläubigern aus der Verarrestierung bzw. Pfändung erwachsen (Art. 96 Abs. 2, Art. 275 SchKG; FELLMANN/MÜLLER, a.a.O., N. 230 zu <ref-law>; vgl. FOËX, in: Basler Kommentar, Bundesgesetz über Schuldbetreibung und Konkurs, 2. Aufl. 2010, N. 30 zu <ref-law>).
3.5 Im vorliegenden Fall ist die Ehe der Gesellschafter geschieden worden. Über die Mitwirkung des Betreibungsamtes in der Phase der Liquidation der einfachen Gesellschaft ist nichts bekannt. Fest steht jedoch, dass die Liegenschaften im Gesamteigentum der Ehegatten-Gesellschafter standen und im Rahmen der Liquidation der Gesellschaft (und der nachfolgenden güterrechtlichen Auseinandersetzung) in das Alleineigentum des Schuldners übergingen.
3.5.1 Die Behauptung des Beschwerdeführers, der verarrestierte Liquidationsanteil habe "im Rahmen der Scheidungsvereinbarung Null" betragen, findet in tatsächlicher Hinsicht keine Grundlage (<ref-law>); eine Rechtsverletzung in der Sachverhaltsfeststellung im Sinne von <ref-law> wird nicht dargetan (<ref-law>). Die untere Aufsichtsbehörde hat vielmehr festgestellt, dass "im Rahmen der Liquidation der einfachen Gesellschaft die vorher zur gesamten Hand zustehenden Grundstücke ins Alleineigentum übertragen wurden", worauf sich die Vorinstanz gestützt hat. Unter diesen Umständen bestehen keine Anhaltspunkte, dass die Rechte des verarrestierenden Gläubigers verletzt worden sind, so dass die Gültigkeit der Liquidation der einfachen Gesellschaft angenommen werden kann, selbst wenn das Betreibungsamt nicht mitgewirkt hätte.
3.5.2 Wenn die kantonalen Aufsichtsbehörden die Pfändbarkeit der Liegenschaften bestätigt haben, haben sie angenommen, dass an die Stelle des verarrestierten Liquidationsanteils der in natura zugeteilte Liquidationserlös getreten ist und dieser das Arrestsubstrat wirksam ersetzt hat. Dass bei der Liquidation des Gemeinschaftsvermögens im Fall, dass der Wert des gepfändeten Anteils nicht in Geld ausgewiesen wird, die zugeteilten Vermögensgegenstände zu verwerten sind, geht aus <ref-law> hervor. Entgegen der Auffassung des Beschwerdeführers ist daher nicht ersichtlich, weshalb - wie hier - bei Liquidation des Gemeinschaftsvermögens die zugeteilten Vermögensgegenstände aus dem Arrest fallen sollen bzw. nicht pfändbar wären. Inwiefern die vorinstanzliche Auffassung mit Bundesrecht unvereinbar sei, legt der Beschwerdeführer nicht dar.
3.6 Damit ist die (überarbeitete) Anmeldung des Betreibungsamtes an das Grundbuchamt, auf den beiden gepfändeten Stockwerkeigentumsanteilen eine Verfügungsbeschränkung (<ref-law>) vorzumerken, nicht zu beanstanden. Ihr lag - wie vom Betreibungsamt in der Folge in der Pfändungsurkunde aufgenommen - eine gültige Pfändung zugrunde.
4. Nach dem Gesagten ist der Beschwerde kein Erfolg beschieden. Ausgangsgemäss trägt der Beschwerdeführer die Verfahrenskosten und schuldet der Beschwerdegegnerin eine angemessene Parteientschädigung (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin mit Fr. 500.-- zu entschädigen.
4. Dieses Urteil wird den Verfahrensbeteiligten und dem Obergericht des Kantons Zürich, II. Zivilkammer, als oberer kantonaler Aufsichtsbehörde über Schuldbetreibung und Konkurs schriftlich mitgeteilt.
Lausanne, 15. April 2013
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Escher
Der Gerichtsschreiber: Levante