Sachverhalt: A. A.a Die X._ AG (Beauftragte; Beschwerdeführerin) hat die Y._ AG (Auftraggeberin; Beschwerdegegnerin), ein im Immobilienbereich tätiges Unternehmen, seit Jahren namentlich in Steuerfragen beraten. Mit Vertrag vom 21. Dezember 2001 verkaufte die Auftraggeberin fünf Stockwerkeigentumseinheiten und einen Miteigentumsanteil am Einkaufszentrum "Z._" in Q._ zum Preis von Fr. 22'500'000.-- an ihre zu 100 % beherrschte Tochtergesellschaft "R._ AG", welche sie im selben Jahr erworben hatte. Aufgrund dieses Verkaufs resultierte in der Erfolgsrechnung der Auftraggeberin für das Jahr 2001 ein Reingewinn von Fr. 11'927'915.--. In der Meinung, dass die im System der zweijährigen Vergangenheitsbemessung geltenden Verrechnungsmöglichkeiten Anwendung fänden, verrechnete die Auftraggeberin in der Steuererklärung für das Jahr 2001 den Reingewinn mit einem Verlustvortrag von Fr. 12'169'671.-- aus den acht vorangegangenen Geschäftsjahren 1993 bis 2000. Damit wäre nach Auffassung der Auftraggeberin für das Steuerjahr 2001 keine direkte Bundessteuer auf dem Gewinn abzurechnen gewesen. A.b Mit dem am 1. Januar 1995 in Kraft getretenen Bundesgesetz vom 14. Dezember 1990 über die direkte Bundessteuer (DBG; SR 642.11) erfolgte indessen ein Wechsel zur Gegenwartsbesteuerung. Die Verlustverrechnungsregeln wurden dabei insofern geändert, als nur noch die Verluste aus den sieben der Steuerperiode vorangegangenen Geschäftsjahren abgezogen werden konnten. Da das DBG keine Übergangsbestimmungen zur Verlustverrechnung enthält, blieb bis Mai 2001 unklar, von welcher Verlustvortragsperiode nach dem Systemwechsel auszugehen war. Die Eidgenössische Steuerverwaltung hielt in ihrem Kreisschreiben Nr. 4 vom 26. November 1992 auf S. 4 zwar fest, dass für die neurechtliche Berechnung die Verluste aus sieben Vorjahren nach den Grundsätzen des neuen Berechnungssystems zu berücksichtigen seien. Nachdem das Kreisschreiben in der Lehre aber kritisiert wurde, gelangte die Eidgenössische Steuerverwaltung schliesslich zur Auffassung, dass das neue Recht die Verlustergebnisse der vor dem 1. Januar 1995 abgeschlossenen Geschäftsjahre "erbe": Die Verluste aus acht Vorjahren sollten bei der Berechnung nach altem Recht berücksichtigt werden können. Sofern dabei ein Verlust verbleibe, der noch nicht verrechnet werden konnte, könne dieser auch im System der Gegenwartsbesteuerung berücksichtigt werden. Mit Urteil 2A.532/1998 vom 17. Mai 2001 stellte sich das Bundesgericht jedoch gegen diese Praxis und schloss sich der ursprünglich von der Eidgenössischen Steuerverwaltung im Kreisschreiben Nr. 4 vertretenen Rechtsauffassung an. Es entschied u.a., dass das neue Recht so zur Anwendung gelange, wie wenn es schon vor 1995 gegolten hätte. Dies hatte zur Folge, dass der Reingewinn nach neurechtlicher Veranlagung ab 1995 nur noch mit Verlusten aus den sieben vorangegangenen Geschäftsjahren verrechnet werden konnte. A.c Mit Schreiben vom 13. August 2001 nahm die Beauftragte mit Blick auf die geplante Veräusserung der genannten Grundstücke an die Tochtergesellschaft "R._ AG" Stellung zu diesem Urteil. Sie hielt dafür, dass die Rechtsprechung des Bundesgerichts keinen Einfluss auf die Möglichkeit habe, die Verluste aus den acht Vorjahren zu verrechnen. Dabei handelte es sich - wie die Beauftragte im Nachhinein eingesteht - um eine Fehleinschätzung. Entsprechend der bundesgerichtlichen Rechtsprechung liess die Steuerverwaltung bei der Auftraggeberin in der Folge nur die Verrechnung mit den Verlustvorträgen aus den Jahren 1994 bis 2000 in der Höhe von Fr. 6'273'741.-- zu und unterbreitete einen Einschätzungsvorschlag, der für das Jahr 2001 von einem Reingewinn von Fr. 5'741'926.-- ausging. Die Beauftragte riet der Auftraggeberin, diese Veranlagung zu akzeptieren. Gemäss provisorischer Steuerrechnung 2001 vom 31. Januar 2003 hatte die Auftraggeberin somit bei einem steuerbaren Reingewinn von Fr. 5'654'174.-- einen Steuerbetrag von Fr. 480'604.80 zu bezahlen. Der aufgrund bewilligter Ratenzahlung geschuldete Verzugszins belief sich nach ihren Angaben auf Fr. 21'483.98, womit ihr insgesamt eine unerwartete Steuerlast von Fr. 502'088.80 entstanden sei. Diese stelle einen Schaden dar. A.d Die Auftraggeberin wurde auch an ihrem Nebensteuerdomizil in Bern zum Satz von Fr. 5'741'900.-- besteuert. Für den im Steuerjahr 2001 erzielten Ertrag von Fr. 481'600.-- wurde ein Steuerbetrag von Fr. 83'741.85 rechtskräftig veranlagt. Hätte der Verlustvortrag aus dem Jahr 1993 verrechnet werden können, so hätte der satzbestimmende Gewinn auch im Kanton Bern Fr. 0.-- betragen, womit nur die Kapitalsteuer von insgesamt Fr. 1'576.55 zu entrichten gewesen wäre. Durch die Besteuerung zum höheren Satz resultierte somit eine steuerliche Mehrbelastung von Fr. 82'165.30. A.e Schliesslich musste eine Tochtergesellschaft der Auftraggeberin im Kanton Genf einen um Fr. 21'244.-- zu hoch ausgefallenen Betrag als Liegenschaftssteuer entrichten, weil die Beauftragte nicht bemerkt hatte, dass der besteuerte Liegenschaftsertrag aus einem verlängerten Geschäftsjahr von 15 Monaten resultierte und nicht auf 12 Monate umgerechnet worden war. Die Steuerrechnung wurde erst an die Auftraggeberin weitergeleitet, als kein Rechtsmittel mehr erhoben werden konnte. Ihren Schadenersatzanspruch trat die Tochtergesellschaft in der Folge an die Auftraggeberin ab. B. B.a Am 7. September 2004 reichte die Auftraggeberin beim Handelsgericht des Kantons Zürich Klage ein mit dem Begehren, die Beauftragte sei zur Zahlung von Fr. 605'498.10 zu verpflichten. Mit Urteil vom 4. April 2008 hiess das Handelsgericht die Klage teilweise gut und verurteilte die Beauftragte zur Zahlung des bei der Genfer Liegenschaftssteuer angefallenen Mehrbetrags von Fr. 21'244.-- (Ziff. 1 Absatz 1), zur Tragung von 19/20 der Verfahrenskosten (Ziff. 3) und zur Zahlung einer Parteientschädigung (Ziff. 4). Im Mehrbetrag wies es die Klage ab (Ziff. 1 Absatz 2). B.b Dagegen erhob die Auftraggeberin beim Kassationsgericht des Kantons Zürich Nichtigkeitsbeschwerde und beantragte, es seien die Dispositiv-Ziff. 1 Absatz 2, Ziff. 3 und 4 aufzuheben und die Sache zur Neubeurteilung an das Handelsgericht zurückzuweisen. Mit Zirkulationsbeschluss vom 13. Februar 2009 wies das Kassationsgericht die Beschwerde ab, soweit es auf sie eintrat, und verurteilte die Auftraggeberin zur Tragung der Verfahrenskosten (Ziff. 3) und zur Zahlung einer Parteientschädigung (Ziff. 4). B.c Mit Beschwerde in Zivilsachen vom 23. März 2009 gegen den Zirkulationsbeschluss des Kassationsgerichts sowie gegen das Urteil des Handelsgerichts beantragte die Auftraggeberin dem Bundesgericht, es sei die Beauftragte zu verpflichten, ihr einen Betrag von Fr. 584'254.10 zu bezahlen, eventualiter sei die Sache zu neuer Beurteilung an das Handelsgericht des Kantons Zürich zurückzuweisen (Verfahren 4A_144/2009). Insoweit das Handelsgericht die Klage guthiess, focht die Auftraggeberin das Urteil nicht an. Sinngemäss verlangte sie damit die Aufhebung der Dispositiv-Ziff. 1 Absatz 2, Ziff. 3 und 4 des Urteils des Handelsgerichts und der Dispositiv-Ziff. 3 und 4 des Zirkulationsbeschlusses des Kassationsgerichts. Mit Urteil 4A_144/2009 vom 6. Oktober 2009 wies das Bundesgericht die Beschwerde gegen das Urteil des Kassationsgerichts ab, hiess die Beschwerde gegen das Urteil des Handelsgerichts aber teilweise gut. Es hob Dispositiv-Ziff. 1 Absatz 2, Ziff. 3 und 4 dieses Urteils auf und wies die Sache zur Ergänzung des Sachverhalts und neuer Entscheidung an das Handelsgericht zurück. C. C.a Mit Beschluss und Urteil vom 16. August 2010 hiess das Handelsgericht des Kantons Zürich die (Rest-)Klage gut und verpflichtete die Beauftragte zur Zahlung von Fr. 584'254.10 an die Auftraggeberin. C.b Gegen dieses Urteil erhob die Beauftragte beim Kassationsgericht des Kantons Zürich Nichtigkeitsbeschwerde und beantragte die Aufhebung des angefochtenen Urteils und die Rückweisung der Sache an das Handelsgericht zur Neubeurteilung. Mit Zirkulationsbeschluss vom 14. Dezember 2011 hiess das Kassationsgericht die Beschwerde teilweise gut und strich die Erwägungen II.4.b und II.4.c, die eine Eventualbegründung enthielten, aus dem Urteil des Handelsgerichts. Im Übrigen wies es die Beschwerde ab, soweit es darauf eintrat. D. Mit Beschwerde in Zivilsachen vom 31. Januar 2012 beantragt die Beauftragte dem Bundesgericht, es seien das Urteil des Handelsgerichts vom 16. August 2010 und der Beschluss des Kassationsgerichts vom 14. Dezember 2011, soweit dieser das Dispositiv des Urteils des Handelsgerichts schütze, aufzuheben und es sei die Klage abzuweisen. Eventualiter sei das Urteil des Handelsgerichts aufzuheben und die Sache zur Durchführung des Beweisverfahrens und zur Neubeurteilung an das Handelsgericht zurückzuweisen. Die Beschwerdeführerin beantragt zudem die Gewährung der aufschiebenden Wirkung. Die Beschwerdegegnerin schliesst in ihrer Vernehmlassung auf Abweisung der Beschwerde. Eventuell seien das Urteil des Handelsgerichts und, soweit damit das Urteil des Handelsgerichts nicht geschützt wurde, das Urteil des Kassationsgerichts aufzuheben und die Sache zur Neubeurteilung an das Handelsgericht zurückzuweisen. Sowohl das Handelsgericht als auch das Kassationsgericht haben auf eine Vernehmlassung verzichtet. Die Parteien reichten unaufgefordert Replik und Duplik ein. E. Mit Präsidialverfügung vom 8. März 2012 wurde das Gesuch um Gewährung der aufschiebenden Wirkung abgewiesen. 