Sachverhalt:
A. Die Parteien haben die gemeinsamen Töchter V._, geb. xxxx 1996, und W._, geb. xxxx 1997. Bei der Scheidung am 16. März 1999 wurden die Töchter entsprechend dem gemeinsamen Antrag der Parteien unter die elterliche Sorge des Vaters gestellt, weil die Mutter seinerzeit mit Drogen in Kontakt stand und mit der Erziehung der Kinder überfordert gewesen wäre. Die Mädchen verbringen den Tag in einem Kinderhort. Auch die Grosseltern väterlicherseits übernehmen einen Teil der Betreuung.
In der Zwischenzeit hat sich die Mutter wieder gefangen. Sie geht einer Erwerbsarbeit nach und hat mit ihrem neuen Partner einen gemeinsamen Sohn. An ihrer jetzigen Erziehungsfähigkeit für V._ und W._ bestehen keine Zweifel.
B. Mit Abänderungsklage vom 1. Juli 2002 hat die Mutter die Zuteilung der elterlichen Sorge über V._ und W._ verlangt. Mit Urteil vom 14. Januar 2003 hat das Bezirksgericht Zurzach die Klage abgewiesen.
An der Appellationsverhandlung vom 30. November 2004 hat die Klägerin eine Anhörung der Parteien und der Kinder beantragt. Das Obergericht wies diese Verfahrensanträge sowie die Klage selbst ab.
C. Gegen dieses Urteil hat die Klägerin am 21. Februar 2005 Berufung eingereicht mit den Begehren um dessen Aufhebung und um Zuteilung der elterlichen Sorge über V._ und W._, unter Einräumung eines Besuchsrechts an den Beklagten und unter dessen Verurteilung zu angemessenen Unterhaltsbeiträgen. In seiner Berufungsantwort vom 15. April 2005 hat der Beklagte auf Abweisung der Berufung geschlossen. Beide Parteien verlangen die unentgeltliche Rechtspflege.

Das Bundesgericht zieht in Erwägung:
1. Die Klägerin beanstandet die unterbliebene Anhörung der Kinder und macht eine Verletzung von <ref-law> sowie von Art. 12 der UNO-Kinderrechtskonvention (KRK, SR 0.107) geltend.
1.1 <ref-law> bestimmt, dass bei Anordnungen über Kinder diese in geeigneter Weise durch das Gericht oder durch eine beauftragte Drittperson persönlich anzuhören sind, soweit nicht ihr Alter oder andere wichtige Gründe dagegen sprechen. Diese Norm findet auf alle gerichtlichen Verfahren Anwendung, in denen Kinderbelange zu regeln sind. Sie gilt demnach nicht nur im Scheidungs-, sondern auch im Eheschutzverfahren sowie namentlich für die vorsorglichen Massnahmen im Sinn von <ref-law> (siehe <ref-ruling>) und im Abänderungsverfahren nach <ref-law>.
Die Anhörung ist Ausfluss der Persönlichkeit des Kindes und somit ein höchstpersönliches Recht (dazu insb. Schütt, Die Anhörung des Kindes im Scheidungsverfahren, Diss. Zürich 2002, S. 50 ff.). Sobald das Kind urteilsfähig ist, nimmt es seinen Anspruch selbst wahr; ab diesem Stadium erhält der Gehörsanspruch die Komponente eines persönlichen Mitwirkungsrechts, welches das Kind insbesondere berechtigt, (auch im Verfahren seiner Eltern) die Anhörung zu verlangen, soweit es betroffen ist (Schütt, a.a.O., S. 51 und 81 ff.; Levante, Die Wahrung der Kindesinteressen im Scheidungsverfahren - die Vertretung des Kindes im Besonderen, Diss. St. Gallen 2000, S. 42; Rumo-Jungo, Die Anhörung des Kindes, in: AJP 1999, S. 1579 und 1589; Bodenmann/Rumo-Jungo, Die Anhörung von Kindern, in: FamPra 2003, S. 24). Daneben dient die Anhörung unabhängig vom Alter des Kindes der (von Amtes wegen vorzunehmenden, vgl. <ref-law>) Ermittlung des Sachverhalts (Reusser, Die Stellung des Kindes im neuen Scheidungsrecht, in: Vom alten zum neuen Scheidungsrecht, Bern 1999, N. 4.75; Freiburghaus, Auswirkungen der Scheidungsrechtsrevision auf die Kinderbelange und die vormundschaftlichen Organe [im Folgenden: Auswirkungen], in: ZVW 1999, S. 141; Schweighauser, in: Praxiskommentar Scheidungsrecht, Basel 2000, N. 7 zu <ref-law>; Schütt, a.a.O., S. 52 f.), weshalb die Eltern die Anhörung des Kindes aufgrund ihrer Parteistellung als Beweismittel anrufen können (Schütt, a.a.O., S. 51 f. und 99; vgl. auch Rumo-Jungo, a.a.O., S. 1579 und 1589; Bodenmann/ Rumo-Jungo, a.a.O., S. S. 24). In dieser Hinsicht geht <ref-law> über Art. 12 KRK hinaus, der ein Meinungsäusserungsrecht in allen das Kind belangenden Verfahren gewährt, soweit dieses fähig ist, sich eine eigene Meinung zu bilden, was nach der Lehre mit der Urteilsfähigkeit im Sinn von <ref-law> gleichzusetzen ist (Bräm, Die Anhörung des Kindes im neuen Scheidungsrecht, in: AJP 1999, S. 1570; vgl. auch Birchler, Die Anhörung des Kindes, in: ZVW 2000, S. 239; Schütt, a.a.O., S. 29 ff. und 68; vgl. schliesslich <ref-ruling> E. 1 S. 371).
Der im Rahmen des revidierten Scheidungsrechts am 1. Januar 2000 in Kraft getretene <ref-law> stellt im Sinn der vorstehenden Ausführungen klar, dass Kinder grundsätzlich anzuhören sind, soweit nicht einer der beiden Ausnahmetatbestände - Alter oder andere wichtige Gründe - gegeben ist (vgl. namentlich: Levante, a.a.O., S. 43; Rumo-Jungo, a.a.O., S. 1581). Insofern ist der vom Obergericht für seinen ablehnenden Entscheid angerufene <ref-ruling> obsolet; dieser Entscheid erging zum alten Scheidungsrecht, wo die Kinderanhörung gesetzlich nicht vorgesehen war, aber Zuteilungswünsche älterer Kinder aufgrund der bundesgerichtlichen Rechtsprechung in die Entscheidfindung miteinzubeziehen waren.
1.2 Das Gesetz selbst legt nicht fest, bis zu welchem Alter von einer Anhörung abzusehen sei; auch der Botschaft zum neuen Scheidungsrecht lässt sich keine konkrete Alterslimite entnehmen.
1.2.1 Auch das Bundesgericht hat bislang kein Schwellenalter für die Anhörung von Kindern festgelegt. In seiner bisherigen Rechtsprechung hat es lediglich festgehalten, die Anhörung eines normal entwickelten 91⁄2-jährigen Kindes sei nicht willkürlich (Entscheid 5P.204/2002 vom 6. August 2002, E. 3.4), während es den Verzicht auf die Anhörung von zehn- und zwölfjährigen Kindern entgegen dem ausdrücklichen Begehren und ohne Angabe von Gründen als willkürlich erachtet hat (Entscheid 5P.112/2001 vom 27. August 2001, E. 4). Hingegen hat das Bundesgericht entschieden, es sei nicht willkürlich, wenn das Gericht davon absehe, ein sieben- bzw. fünfjähriges Kind, das bereits im Rahmen einer psychologischen Begutachtung befragt worden und im Übrigen durch die chronische Auseinandersetzung zwischen den Eltern stark belastet war, erneut anzuhören (Entscheid 5P.322/2003 vom 18. Dezember 2003, E. 3.2). Sodann hat es den Verzicht auf die Anhörung eines knapp sechsjährigen Kindes geschützt, weil dieses bis anhin nie Kontakt zum Vater gehabt hatte und sich deshalb keine eigene Meinung bilden konnte (<ref-ruling>); bei diesem Fall gilt es im Übrigen zu beachten, dass einzig eine Verletzung von Art. 12 KRK zu prüfen war, der im Gegensatz zu <ref-law> die Urteilsfähigkeit des Kindes voraussetzt (vgl. Ziff. 1.1).
In der gelebten kantonalen Rechtspraxis scheint ein grosser Teil der Gerichte bis zum elften bzw. zwölften Altersjahr von einer Anhörung abzusehen, wenn die Zuteilung der Kinder unstrittig ist und keine Anhaltspunkte bestehen, dass durch die gewählte Lösung das Kindeswohl gefährdet wird (vgl. Birchler, a.a.O., S. 240; Schütt, a.a.O., S. 71; Staubli, Anhörung und Mitwirkung von Kindern und Jugendlichen in allen sie betreffenden Verfahren, insbesondere im Scheidungsverfahren, in: Kinderrechte - Kinderschutz, Basel 2002, S. 98; Suter, L'audition de l'enfant en procédure matrimoniale, in: RJJ 2002, S. 33).
In der Literatur gehen die Meinungen zur Frage, bis zu welchem Alter in jedem Fall von einer Anhörung abzusehen sei, auseinander. Auf die deutsche Praxis verweisend, nach der Kinder teilweise ab dem zweiten und jedenfalls ab dem dritten Lebensjahr angehört werden, plädieren einige Autoren für eine Anhörung ab diesem Alter (Breitschmid, Kind und Scheidung der Elternehe, in: Das neue Scheidungsrecht, Zürich 1999, S. 123 f.; vgl. auch Jaccottet Tissot, L'audition de l'enfant, in: FamPra 2000, S. 83) oder jedenfalls ab einem solchen von fünf bis sechs Jahren (Bodenmann/Rumo-Jungo, a.a.O., S. 26; derselbe, a.a.O., S. 1582; Rumo-Jungo, Das Kind und die Scheidung seiner Eltern: ausgewählte Fragen, in: Kindeswohl, Zürich 2003, S. 156; Zimmermann, Le témoignage d'enfants dans le contexte juridique: la question de la suggestibilité, in: RVJ 2002, S. 126; vgl. auch Sutter/Freiburghaus, Kommentar zum neuen Scheidungsrecht, Zürich 1999, N. 35 zu <ref-law>). Der wohl überwiegende Teil der Lehre plädiert für eine Anhörung nicht vor sechs bzw. sieben Jahren (Freiburghaus, Auswirkungen, S. 142; derselbe, Der Einfluss des Übereinkommens auf die schweizerische Rechtsordnung, in: Die Rechte des Kindes, 2001, S. 195; Hausheer, Die wesentlichen Neuerungen des neuen Scheidungsrechts, in: ZBJV 135, S. 29; auf Letzteren verweisend: Reusser, a.a.O., N. 4.79; Levante, a.a.O., S. 43 f.).
1.2.2 Das Gesetz spricht von einer "Anhörung", was semantisch eine verbale Äusserung des Kindes voraussetzt; die blosse "Anschauung" oder Beobachtung des Kindes wird diesem Erfordernis nicht gerecht. Folglich setzt die Anhörung ein entsprechendes Alter des Kindes voraus und insofern ist sie von der kinderpsychiatrischen Begutachtung abzugrenzen, bei der die Beobachtung des Kindes eine von mehreren Erkenntnisquellen darstellen kann und für deren Anordnung kein bestimmtes Mindestalter vorausgesetzt ist.
Auf der anderen Seite ist das Schwellenalter für die Anhörung aber auch zu unterscheiden von der kinderpsychologischen Erkenntnis, dass formallogische Denkoperationen erst ab ungefähr elf bis dreizehn Jahren möglich sind und auch die sprachliche Differenzierungs- und Abstraktionsfähigkeit erst ab ungefähr diesem Alter entwickelt ist (vgl. Felder/Nufer, Die Anhörung des Kindes aus kinderpsychologischer Sicht, in: Vom alten zum neuen Scheidungsrecht, Bern 1999, N. 4.131; dieselben, Richtlinien für die Anhörung des Kindes aus kinderpsychologischer/kinderpsychiatrischer Sicht gemäss Art. 12 der UNO-Konvention über die Rechte des Kindes, in: SJZ 1999, S. 318; Nufer, Die Kommunikationssituation bei der Anhörung von Kindern, in: SJZ 1999, S. 317, sowie in: ZVW 1999, S. 209). Die Anhörung setzt nicht voraus, dass das Kind im Sinn von <ref-law> urteilsfähig ist. Bei kleineren Kindern ist auch nicht nach konkreten Zuteilungswünschen zu fragen, können sich diese doch hierüber noch gar nicht losgelöst von zufälligen gegenwärtigen Einflussfaktoren äussern und in diesem Sinn eine stabile Absichtserklärung abgeben (vgl. Arntzen, Elterliche Sorge und Umgang mit Kindern, München 1994, S. 12 und 65; Felder/ Nufer, Richtlinien, S. 318; dieselben, Anhörung, N. 4.131). Die Aussagen jüngerer Kinder haben deshalb für die Zuteilungsfrage nur einen beschränkten Beweiswert (Hausheer, a.a.O., S. 29; Reusser, a.a.O., N. 4.79). Bei ihnen geht es in erster Linie darum, dass sich das urteilende Gericht ein persönliches Bild machen kann und über ein zusätzliches Element bei der Sachverhaltsfeststellung und Entscheidfindung verfügt (vgl. Bräm, a.a.O., S. 1569; Schweighauser, a.a.O., N. 7 zu <ref-law>; Felder/Nufer, Anhörung, N. 4.128).
1.2.3 Aus den genannten Gründen geht das Bundesgericht im Sinn einer Richtlinie davon aus, dass die Kinderanhörung grundsätzlich ab dem vollendeten sechsten Altersjahr möglich ist. Indes ist nicht von vornherein ausgeschlossen, dass sich je nach den konkreten Umständen auch die Anhörung eines etwas jüngeren Kindes aufdrängen könnte, etwa wenn von mehreren Geschwistern das jüngste kurz vor dem genannten Schwellenalter steht.
1.2.4 Vorliegend hatte die Klägerin die Einvernahme der sieben- und neunjährigen Mädchen beantragt. Weil die Anhörung als Pflichtrecht ausgestaltet ist (vgl. Rumo-Jungo, Anhörung, S. 1579), wäre das Obergericht folglich - unter Vorbehalt anderer wichtiger Gründe (dazu Ziff. 1.3) - in Anwendung von <ref-law> zur Anhörung der beiden Kinder verpflichtet gewesen. Mit seiner Begründung, die Kinder seien zu einer Stellungnahme noch gar nicht in der Lage und ihren Aussagen könnte ohnehin kein bedeutendes Gewicht beigemessen werden, verkennt das Obergericht die grundsätzliche Bedeutung und den persönlichkeitsrechtlichen Aspekt der Kinderanhörung. Nichts anderes ergibt sich aus dem vom Obergericht aufgeführten <ref-ruling>, wurde doch in jenem Fall von der (erneuten) Einvernahme eines neunjährigen Kindes, das seinen Vater kaum je gesehen hatte, im Wesentlichen deshalb abgesehen, weil es bereits im Rahmen eines umfassenden Gutachtens durch einen Kinderpsychiater befragt worden war.
1.3 Nebst dem Kindesalter kann auch aus anderen wichtigen Gründen, die das Gesetz wiederum nicht näher spezifiziert, von der Anhörung abgesehen werden.
1.3.1 Die Botschaft nennt beispielhaft die Ablehnung der Anhörung durch das Kind als wichtigen Grund (BBl 1996 I 144), wobei sicherzustellen wäre, dass das Kind dabei nicht durch einen Elternteil beeinflusst ist. Die Literatur nennt als weitere wichtige Gründe den begründeten Verdacht auf Repressalien gegenüber dem Kind, dessen dauernder Aufenthalt im Ausland, die Beeinträchtigung von dessen Gesundheit durch die Anhörung sowie die besondere Dringlichkeit der Anordnungen (vgl. namentlich: Reusser, a.a.O., N. 4.85; Zimmermann, a.a.O., S. 126; Baltzer-Bader, Die Anhörung des Kindes - praktisches Vorgehen, in: AJP 1999, S. 1576). Schliesslich würde es keinen Sinn machen, ein Kind anzuhören, das geistig behindert oder in seiner Entwicklung in einer Weise retardiert ist, dass seinen Ausführungen kein Aussagewert beigemessen werden könnte. Hingegen würde es nicht angehen, auf die Anhörung mit dem (nicht weiter belegten) Vorwand zu verzichten, man wolle dem Kind die Belastung ersparen (Bräm, a.a.O., S. 1571; Rumo-Jungo, Anhörung, S. 1582).
1.3.2 Das Obergericht hat bei seinem ablehnenden Entscheid unter anderem auf die Briefchen der Kinder - nach dem einen möchten sie gerne bei der Mutter wohnen, nach dem andern freuen sie sich, beim Vater zu leben - und die Zeugenaussage der Leiterin des Kinderhorts verwiesen, wonach der betreffende Entscheid für die Mädchen ein Problem sei, weil sie keinem der Elternteile wehtun möchten. Das Gericht hat daraus gefolgert, dass die Kinder in einem Loyalitätskonflikt stünden und die Anhörung für sie eine Belastung darstellen würde.
1.3.3 Im Normalfall sind Kinder beiden Elternteilen gleichermassen zugeneigt und sie wünschen sich in Trennungssituationen deren Wiedervereinigung (Arntzen, a.a.O., S. 1 f.). Deshalb steht fast jedes Scheidungskind in einem latenten oder offenen Loyalitätskonflikt, der sich mehr oder weniger belastend auswirkt. Insofern könnte die Kinderanhörung mit dem blossen Verweis auf die - letztlich bei jedem familienrechtlichen Verfahren auf die eine oder andere Weise bestehende - Belastungssituation systematisch unterlaufen werden. Nicht zu übersehen ist in diesem Zusammenhang schliesslich die Tatsache, dass in aller Regel nicht die (einmalige) Anhörung, sondern die (gegebenenfalls chronisch konfliktbeladene) Familiensituation die eigentliche Belastung für das Kind darstellt. Deshalb darf von einer beantragten Anhörung nur dann abgesehen werden, wenn - nebst anderen möglichen Gründen (dazu Ziff. 1.3.1) - eine eigentliche Beeinträchtigung der physischen oder psychischen Gesundheit des Kindes zu befürchten ist. Aus dem für das Bundesgericht verbindlich festgestellten Sachverhalt (Art. 63 Abs. 2 OG) gehen keine Anzeichen für eine Belastung hervor, die über das hinausginge, was jedem Verfahren, in welchem Kinderbelange zu regeln sind, inhärent ist.
1.4 Aus dem Gesagten ergibt sich, dass das Obergericht mit der Verweigerung der von der Klägerin beantragten Kindesanhörung <ref-law> verletzt hat.
2. Die Klägerin macht ferner eine Verletzung von Art. 134 (neue Zuteilung der elterlichen Sorge), von Art. 144 Abs. 1 (Anhörung der Eltern) und von <ref-law> (Untersuchungsgrundsatz) geltend.
Nach <ref-law> kann die Zuteilung der elterlichen Sorge neu geregelt werden, wenn dies wegen wesentlicher Veränderung der Verhältnisse zum Wohl des Kindes geboten ist. Eine Neuregelung setzt somit nicht allein die wesentliche Veränderung der Verhältnisse voraus; vielmehr muss sie auch zum Wohl des Kindes geboten sein. Nach der Rechtsprechung des Bundesgerichts zu Art. 157 aZGB, an die für das neue Recht angeknüpft werden kann (Wirz, in: Praxiskommentar Scheidungsrecht, Basel 2000, N. 11 zu <ref-law>), kommt eine Änderung des Sorgerechts nur in Betracht, wenn die Beibehaltung der bisherigen Regelung sich offensichtlich nachteilig auf das Wohl der Kinder auswirken und das Kindeswohl ernsthaft gefährden würde. Eine Neuregelung setzt in diesem Sinn voraus, dass die Veränderung der Verhältnisse zwingend eine solche gebietet, weil die geltende Regelung dem Kind mehr schadet als der mit der Änderung der Hauptbezugspersonen verbundene Verlust an Kontinuität in der Erziehung und den Lebensumständen (vgl. <ref-ruling> E. 1 S. 77 f.; <ref-ruling> E. 4c S. 380; 111 I 313 E. 4 S. 316).
Aus der kantonalen Sachverhaltsfeststellung sind keine Anzeichen für eine Gefährdung des Kindeswohls ersichtlich. Vielmehr ergibt sich, dass der Beklagte mit dem Kinderhort für die Gegenwart und die nächsten Jahre eine angemessene Lösung gefunden hat und sich die Mädchen dort wohlfühlen. Sodann hat das Obergericht aufgrund übereinstimmender Zeugenaussagen festgehalten, dass die Hauptlast der Kindererziehung nicht bei den Grosseltern, sondern beim Vater liegt, und es hat auch festgestellt, dass die Betreuung der beiden Mädchen insgesamt gut klappt und diese eine normale Entwicklung aufweisen.
Indes können sich aus der noch durchzuführenden Anhörung der Kinder neue Sachverhaltselemente ergeben, die im Rahmen der von <ref-law> statuierten Offizialmaxime nach weiteren Abklärungen oder Beweismassnahmen wie der Einvernahme der klägerischerseits beantragten Zeugen rufen. Sodann umfasst die Anhörung der Eltern gemäss <ref-law> insbesondere auch einen Anspruch, zu den Aussagen des Kindes Stellung nehmen zu können (Sutter/ Freiburghaus, a.a.O., N. 10 zu <ref-law>). Weil die Kinder bislang nicht angehört worden sind, steht der Klägerin unabhängig von der Frage, ob ein grundsätzlicher Anspruch auf erneute Anhörung durch die obere Instanz bestünde, ein Äusserungsrecht zu.
Demnach ist jedenfalls <ref-law> verletzt. Im Übrigen sind gestützt auf <ref-law> gegebenenfalls weitere Beweismassnahmen nötig.
3. Nach dem Gesagten ist die Berufung dahingehend gutzuheissen, dass das angefochtene Urteil aufgehoben und die Sache im Sinn der Erwägungen an die Vorinstanz zurückgewiesen wird. Bei diesem Verfahrensausgang wird der Beklagte kosten- und entschädigungspflichtig (Art. 156 Abs. 1 und Art. 159 Abs. 2 OG). Beiden Parteien ist die unentgeltliche Rechtspflege zu erteilen, je unter Beiordnung des sie vertretenden Rechtsbeistandes (Art. 152 Abs. 1 und 2 OG).

Demnach erkennt das Bundesgericht:
1. Die Berufung wird dahingehend gutgeheissen, dass das angefochtene Urteil aufgehoben und die Sache im Sinn der Erwägungen an die Vorinstanz zurückgewiesen wird.
2. Beiden Parteien wird die unentgeltliche Rechtspflege erteilt, je unter Beiordnung des sie vertretenden Rechtsbeistandes.
3. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beklagten auferlegt, jedoch einstweilen auf die Bundesgerichtskasse genommen.
4. Dr. Andreas Edelmann, Fürsprecher, und Annegret Lautenbach-Koch, Rechtsanwältin, werden aus der Bundesgerichtskasse mit je Fr. 2'000.-- entschädigt.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Aargau, 1. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 1. Juni 2005
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: