Sachverhalt: A. A.a X._, Zug, (Klägerin, Beschwerdeführerin) war Aktionärin der Z._ SA mit Sitz in Neuenburg. Sie hielt 50 % der Aktien; die anderen 50 % gehörten ihrem Bruder. Im November 1988 beauftragten die Geschwister den damaligen Schweizerischen Bankverein (nunmehr UBS AG) damit, einen Käufer für die Aktien zu suchen und es konnte mit der W._-Gruppe eine Interessentin gefunden werden. Die Z._ SA verfügte mit rund Fr. 28 Mio. über sehr viel Liquidität. Die W._ Holding AG schlug zunächst vor, die Gesellschaft ohne diese Liquidität zu kaufen. Diesen Vorschlag lehnten die Verkäufer ab. Im August 1989 kam ein Vorvertrag zustande, in dem ein Preis von Fr. 40 Mio. für alle Aktien vereinbart wurde. Dieser Preis wurde im Oktober 1989 auf Fr. 37 Mio. reduziert. Mit Schreiben vom 22. November 1989 beauftragte der Schweizerische Bankverein die Schweizerische Treuhandgesellschaft (STG), deren Verbindlichkeiten später durch die Y._ AG, Zürich, (Beklagte, Beschwerdegegnerin) übernommen wurden, zur Frage der Besteuerung des Verkaufs Stellung zu nehmen. Die STG bestätigte mit Schreiben vom 27. November 1989, die geplante Transaktion habe "aucune conséquence fiscale pour nos clients". Am 18. Dezember 1989 wurde der Kaufvertrag abgeschlossen. Für die W._-Gruppe trat als Käuferin die (damals noch in Gründung befindliche) V._ SA, Neuenburg, auf. Der Preis für die von der Klägerin gehaltenen 50 % der Aktien wurde auf Fr. 18.62 Mio. festgelegt. Die Finanzierung des Kaufpreises erfolgte in der Weise, dass die Käuferin V._ SA ein Darlehen von Fr. 25 Mio. vom damaligen Bankverein erhielt, das durch die Verpfändung einer Festgeldanlage der übernommenen Z._ SA sichergestellt wurde. A.b Im Jahre 1992 wurde die Transaktion von der Steuerverwaltung von Neuenburg als indirekte Teilliquidation besteuert. Die Klägerin wehrte sich zunächst gegen diese Besteuerung, musste aber mit der Zeit einsehen, dass dies erfolglos war und bezahlte schliesslich Steuern von rund Fr. 1.75 Mio. Sie vertrat in der Folge die Meinung, dass diese Steuerpflicht, erhöht um Zinsen und Kosten, einen Schaden darstelle, für den die Beklagte hafte. B. B.a Mit Klage vom 24. Januar 2005 beim Zivilgericht Basel-Stadt verlangte die Klägerin, es sei die Beklagte zur Zahlung von Fr. 1 Mio. zuzüglich Zins zu 5 % ab Klageeinreichung zu verurteilen. Mit Zwischenurteil vom 23. August 2006 stellte das Zivilgericht fest, dass die Beklagte passivlegitimiert sei. Dieser Zwischenentscheid wurde - nach einem ersten, vom Bundesgericht aufgehobenen Entscheid des Appellationsgerichts (Urteil 4A_256/2008 vom 29. Oktober 2008) - vom Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 23. Januar 2009 bestätigt. Mit Urteil vom 1. September 2010 hiess das Zivilgericht Basel-Stadt die Klage gut und verurteilte die Beklagte, der Klägerin Fr. 1 Mio., zuzüglich Zins zu 5 % ab dem 24. Januar 2005, zu bezahlen. B.b Mit Entscheid vom 10. Februar 2012 hiess das Appellationsgericht des Kantons Basel-Stadt eine von der Beklagten gegen dieses Urteil des Zivilgerichts erhobene Berufung gut und wies die Klage ab. Das Appellationsgericht erwog zunächst, es handle sich beim Beizug der Beklagten durch die beauftragte Bank um eine erlaubte Substitution, weshalb die Beklagte der Klägerin grundsätzlich für einen vertragswidrig verursachten Schaden hafte. Mit ihrer sorgfaltswidrigen Falschauskunft hinsichtlich der Steuerfolgen der fraglichen Transaktion sei der Beklagten zudem eine Vertragsverletzung vorzuwerfen. Das Appellationsgericht verneinte hingegen, dass der Klägerin aus der sorgfaltswidrigen Auskunft ein Schaden entstanden sei; das Gericht hielt nach Prüfung der verschiedenen von der Klägerin vorgebrachten Handlungsalternativen fest, es sei ihr der Nachweis nicht gelungen, dass bei Kenntnis der Besteuerungsgefahr eine entschädigungslose Steuerbefreiung hätte bewirkt werden können. C. Mit Beschwerde in Zivilsachen beantragt die Klägerin dem Bundesgericht, es sei der Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 10. Februar 2012 aufzuheben und die Klage gutzuheissen. Eventualiter sei der angefochtene Entscheid aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Die Vorinstanz beantragt in ihrer Vernehmlassung sinngemäss ebenfalls die Abweisung der Beschwerde. Die Beschwerdeführerin hat dem Bundesgericht am 28. August 2012 eine Replik, die Beschwerdegegnerin am 13. September 2012 eine Duplik eingereicht.