Sachverhalt:
A. A.a Im Konkurs über X._ erhielt die Bank Y._ einen Verlustschein im Betrag von Fr. 197'715.65. Gestützt auf den Konkursverlustschein leitete die Bank beim Betreibungsamt der Stadt-Basel die Betreibung ein, worauf X._ Rechtsvorschlag erhob mit der Begründung, sie sei nicht zu neuem Vermögen gekommen. Am 26. August 2008 stellte das Zivilgericht Basel-Stadt fest, dass X._ mit Bezug auf die Betreibung Nr. 1 vom 14. April 2008 im Umfang von Fr. 13'400.-- zu neuem Vermögen gekommen ist, und verweigerte im gleichen Umfang den Rechtsvorschlag in der erwähnten Betreibung; im diesen Betrag übersteigenden Umfang wurde der Rechtsvorschlag mangels neuen Vermögens bewilligt. Gestützt auf dieses Urteil (sowie nach Rückzug des ordentlichen Rechtsvorschlages) verlangte die Bank die Fortsetzung der Betreibung im Umfang von Fr. 13'400.--.
A.b Am 26. Februar 2009 vollzog das Betreibungsamt gegenüber X._ in der von der Bank eingeleiteten Betreibung die Pfändung. Dabei wurde das Existenzminimum der Schuldnerin auf Fr. 4'553.-- festgesetzt und ihr darüber liegendes Einkommen im Umfang von monatlich Fr. 3'140.-- gepfändet (Pfändungsurkunde vom 7. April 2009).
B. Gegen die Pfändung erhob X._ Beschwerde und verlangte, die Lohnpfändung sei auf monatlich Fr. 1'116.-- herabzusetzen, im Wesentlichen mit der Begründung, die Pfändung des festgestellten neuen Vermögens von Fr. 13'400.-- sei anteilsmässig auf das Lohnpfändungsjahr zu verteilen. Die Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt wies die Beschwerde mit Urteil vom 19. Mai 2009 ab.
C. Mit Eingabe vom 21. September 2009 (Postaufgabe) hat X._ Beschwerde in Zivilsachen erhoben. Die Beschwerdeführerin beantragt dem Bundesgericht, das Urteil der kantonalen Aufsichtsbehörde sei aufzuheben und die Lohnpfändung auf monatlich Fr. 1'116.-- festzusetzen. Weiter ersucht sie um unentgeltliche Rechtspflege.
Die kantonale Aufsichtsbehörde hat auf eine Vernehmlassung verzichtet. Die Bank Y._ (Beschwerdegegnerin) beantragt die Abweisung der Beschwerde

Erwägungen:
1. 1.1 Entscheide in Schuldbetreibungs- und Konkurssachen unterliegen der Beschwerde in Zivilsachen (<ref-law>). Beschwerdeentscheide der kantonalen Aufsichtsbehörden über eine Verfügung eines Vollstreckungsorganes gemäss <ref-law> - wie die Pfändung - stellen einen Endentscheid im Sinne von <ref-law> dar (<ref-ruling> E. 1.2 S. 351). Die Beschwerde in Zivilsachen ist grundsätzlich zulässig.
1.2 Die (einzige) kantonale Aufsichtsbehörde über das Betreibungs- und Konkursamt wird durch drei Präsidenten des Zivilgerichts, d.h. des unteren Gerichts des Kantons Basel-Stadt gebildet (§ 5 EG SchKG/ BS; vgl. I. Teil des GOG/BS). Dass das angefochtene Urteil nicht vom oberen kantonalen Gericht ausgeht, ändert an der Zulässigkeit der Beschwerde in Zivilsachen nichts, da die Frist zur Anpassung an die Anforderungen des BGG noch nicht abgelaufen ist (Art. 75 Abs. 2, Art. 130 Abs. 2 BGG).
1.3 Die Beschwerdeführerin verlangt die Herabsetzung der pfändbaren Lohnquote pro Monat. Die Beschwerdeführerin hat ein nach <ref-law> geschütztes Interesse und ist zur Beschwerde in Zivilsachen berechtigt (<ref-law>).
1.4 In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Mit der Beschwerde kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>).
2. Die Aufsichtsbehörde hat im Wesentlichen erwogen, dass in der gestützt auf den Konkursverlustschein eingeleiteten Betreibung, in welcher der Richter (gemäss <ref-law>) den Rechtsvorschlag teilweise nicht bewilligt und neues Vermögen festgestellt hat, die Gläubigerin das Recht habe, im betreffenden Umfang das Betreibungsverfahren weiterzuführen. Die nachfolgende Einkommenspfändung habe das Betreibungsamt zu Recht nach den üblichen Regeln vorgenommen, unabhängig davon, ob es sich um eine Konkursforderung handle oder nicht. Das Vorgehen des Betreibungsamtes und das auf über Fr. 4'500.-- festgesetzte Existenzminimum nach <ref-law> seien nicht zu beanstanden.
Die Beschwerdeführerin hält demgegenüber fest, in der vorliegenden Betreibung könne sie trotz Feststellung neuen Vermögens in der nachfolgenden Pfändung nicht auf das betreibungsrechtliche Existenzminimum gesetzt werden. Der angefochtene Entscheid verletze <ref-law>, weil der in dieser Bestimmung festgelegte Schutz des Konkursiten bzw. der Zweck der wirtschaftlichen Erholung zunichte gemacht werde.
3. Anlass zur vorliegenden Beschwerde gibt die gegenüber der Beschwerdeführerin vollzogene Pfändung in einer gestützt auf den Konkursverlustschein eingeleiteten Betreibung, welche nach (teilweiser) Verweigerung des Rechtsvorschlages und Feststellung neuen Vermögens fortgesetzt wurde. Unbestritten ist, dass das Betreibungsamt dem Begehren um Fortsetzung der Betreibung für Fr. 13'400.--, d.h. im Umfang, in dem der Richter neues Vermögen der Beschwerdeführerin festgestellt hat, Folge zu leisten hatte. Einziger Streitpunkt ist, welche rechtlichen Regeln für die nachfolgende Pfändung massgebend sind bzw. ob das Betreibungsamt das pfändbare Einkommen der Beschwerdeführerin einzig nach <ref-law> festzusetzen hat.
3.1 Die Beschwerdeführerin führt zu Recht aus, dass nach Beendigung des Konkurses eine Forderung erst wieder geltend gemacht werden kann, wenn der Schuldner zu neuem Vermögen gekommen ist (<ref-law>). Mit dieser Einschränkung der Geltendmachung der Konkursforderungen - welche das Gesetz bereits vor der Teilrevision von 1994 vorsah - soll dem Schuldner die Möglichkeit gegeben werden, sich wirtschaftlich und finanziell zu erholen (<ref-ruling> E. 1 S. 94; <ref-ruling> E. 3.1 S. 622; <ref-ruling> E. 2.1 S. 425; vgl. FRITZSCHE/WALDER, Schuldbetreibung und Konkurs nach schweizerischem Recht, Bd. II, 1993, § 53 Rz. 6 ff.). Es trifft daher zu, dass die Beschwerdeführerin als ehemalige Konkursitin Anspruch auf eine standesgemässe Lebensführung hat, welche es ihr erlaubt, eine neue Existenz aufzubauen (BGE <ref-ruling> E. 2.1 S. 425). Die Beschwerdeführerin übergeht allerdings, dass als "neues Vermögen" im Sinne von <ref-law> der Überschuss der nach Schluss des Konkurses erworbenen Aktiven über die neuen Passiven gilt, und darunter auch der zur Führung eines standesgemässen Lebens übersteigende Arbeitserwerb fällt (BGE <ref-ruling> E. 2.1 S. 425; FRITZSCHE/WALDER, a.a.O., § 53 Rz. 16). Der Erholungszweck wird bei der Ermittlung des Überschusses gewährleistet. Vorliegend hat der Richter das Vorhandensein von neuem Vermögen der Beschwerdeführerin verbindlich festgestellt.
3.2 Wenn der Richter den Rechtsvorschlag des Schuldners, wonach er nicht zu neuem Vermögen gekommen sei, nicht bewilligt, wird der Umfang des neuen Vermögens festgestellt (<ref-law>) und der Gläubiger kann die Betreibung entsprechend fortsetzen (vgl. BGE 79 Ia 113 E. 4 S. 116; GILLIÉRON, Commentaire de la loi fédérale sur la poursuite pour dettes et la faillite, 2001, N. 7 a.E. zu <ref-law>). Die gerichtliche Feststellung neuen Vermögens beschränkt umfangmässig die Haftung des Schuldners im Rahmen der hängigen Betreibung. Im Rahmen dieser Beschränkung der Betreibung hat der Schuldner jedoch mit seinem ganzen Vermögen einzustehen. Deshalb hat das Betreibungsamt die Pfändung nach <ref-law> - wie nach Eingang eines anderen Fortsetzungsbegehrens - vorzunehmen (JEANDIN, in: Commentaire romand, Poursuite et faillite, 2005, N. 28 zu <ref-law>, N. 27 zu <ref-law>; NÄF, in: Kurzkommentar SchKG, 2009, N. 7 zu <ref-law>; FRITZSCHE/WALDER, a.a.O., § 53 Rz. 16 a.E. und Fn. 39; FÜRSTENBERGER, Einrede des mangelnden und Feststellung neuen Vermögens nach revidiertem Schuldbetreibungs- und Konkursgesetz, Basel 1999, S. 30 f., 93, 149, 156 f.).
3.3 Entgegen der Auffassung der Beschwerdeführerin stellt <ref-law> für die nachfolgende Pfändung keine zusätzlichen Vorschriften, wie ein "Existenzminimum zweiter Ordnung" auf (FÜRSTENBERGER, a.a.O., mit Hinw.), sondern es handelt sich bei der Feststellung neuen Vermögens und der nachfolgenden Pfändung um verschiedene Vorgänge (vgl. <ref-ruling> E. 3c S. 20; JEANDIN, a.a.O., N. 28 zu <ref-law>). Daran hat das neue Recht grundsätzlich nichts geändert. Durch die Einführung der wirtschaftlichen Betrachtungsweise (Art. 265 Abs. 2 a.E. SchKG) und das neu geregelte Verfahren zur Feststellung neuen Vermögens (vgl. <ref-law>) sollte vielmehr die Position des Gläubigers gestärkt werden (vgl. BBl 1991 III 157 ff.). Es bestehen keine Anhaltspunkte, dass das neue Recht den Schuldner im Fall, dass er zwar zu neuem Vermögen gekommen ist und die Betreibung nur in diesem begrenzten Umfang fortgesetzt werden kann, in einer nachfolgenden Pfändung zusätzlich schonen wollte. Die Prüfung der Pfändbarkeitsvoraussetzungen durch das Betreibungsamt ist nur dort beschränkt, wo - anders als im konkreten Fall - der Richter nach Art. 265a Abs. 3 zweiter Satz SchKG sogar Vermögenswerte Dritter, über die der Schuldner wirtschaftlich verfügt, direkt als pfändbar erklärt (GASSER, Nachlassverfahren, Insolvenzerklärung und Feststellung neuen Vermögens, ZBJV 1996 S. 22 f.). Wenn die Vorinstanz demnach festgehalten hat, die Pfändung in der Betreibung für eine Konkursverlustscheinforderung unterscheide sich nach Verweigerung des Rechtsvorschlages betreffend fehlenden neuen Vermögens nicht von der Pfändung für eine andere Forderung, und das Betreibungsamt habe nur <ref-law> zu beachten, stellt dies keine Verletzung von Bundesrecht dar.
3.4 Die Beschwerdeführerin stellt die Wirksamkeit der gesetzlichen Regelung in Frage. Obwohl sie sich wirtschaftlich erholt habe, könne die Beschwerdegegnerin als Gläubigerin der Konkursforderung dennoch wieder - wenn auch umfangmässig beschränkt - von neuem auf ihr Einkommen zugreifen und ihr nur das Notwendigste belassen. Die Beschwerdeführerin übernimmt damit die Kritik der Lehre, welche von einem unbefriedigenden Rechtszustand spricht, weil die blosse Einschränkung der Geltendmachung der Konkursverlustscheinsforderungen keinen hinreichenden Anreiz gebe, einen wirtschaftlichen Neuanfang anzustreben (MEIER, Die dogmatische Situation des Vollstreckungsrechts aus der Sicht des schweizerischen Rechts, in: Zeitschrift für Zivilprozess, Köln, 2008 S. 447 f.). Deshalb werden Vorschläge für die Regelung einer Restschuldbefreiung gemacht (MEIER, a.a.O., S. 451 ff.) oder sei de lege ferenda zu überlegen, ob im SchKG für die nachfolgende Pfändung nicht direkt eine spezielle Existenzminimumsordnung zu Gunsten des Konkursiten aufgenommen werden könnte (FÜRSTENBERGER, a.a.O., S. 31 f.). Diese Kritik und Vorschläge ändern nichts daran, dass nach geltendem Recht der Gläubiger, dessen Forderung vor Konkurseröffnung entstanden ist, in dem Umfang, in welchem der Richter neues Vermögen festgestellt hat, in der nachfolgenden Pfändung gegen den Schuldner wie ein Gläubiger zu behandeln ist, dessen Forderung erst nach der Konkurseröffnung entstanden ist. In beiden Fällen kann der Schuldner gemäss <ref-law> bis zum Existenzminimum gepfändet werden.
3.5 Nach dem Dargelegten hat die Aufsichtsbehörde mit dem angefochtenen Entscheid weder Art. 265 f. noch <ref-law> verletzt, wenn sie die angefochtene Pfändung bestätigt hat. Die Beschwerde ist unbegründet.
4. Aus diesen Gründen ist der Beschwerde kein Erfolg beschieden. Bei diesem Verfahrensausgang wird die Beschwerdeführerin kostenpflichtig (<ref-law>). Eine Parteientschädigung an die Beschwerdegegnerin ist vorliegend nicht gerechtfertigt (Art. 68 Abs. 1 und 2 BGG). Die Voraussetzungen zur Gewährung der unentgeltlichen Rechtspflege sind gegeben (Art. 64 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in Zivilsachen wird abgewiesen.
2. Das Gesuch der Beschwerdeführerin um unentgeltliche Rechtspflege wird gutgeheissen.
3. Es werden keine Gerichtskosten erhoben.
4. Rechtsanwalt Daniel Altermatt wird als unentgeltlicher Anwalt der Beschwerdeführerin bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 1'500.-- ausgerichtet.
5. Dieses Urteil wird den Parteien, dem Betreibungsamt Basel-Stadt und der Aufsichtsbehörde über das Betreibungs- und Konkursamt Basel-Stadt schriftlich mitgeteilt.
Lausanne, 4. Dezember 2009
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Escher Levante