Sachverhalt: A. A.a Die Y._ AG (Beschwerdegegnerin; vormals YA._) hat die X._ AG (Beschwerdeführerin), ein im Immobilienbereich tätiges Unternehmen, seit Jahren namentlich in Steuerfragen beraten. Mit Vertrag vom 21. Dezember 2001 verkaufte die Beschwerdeführerin fünf Stockwerkeigentumseinheiten und einen Miteigentumsanteil am Einkaufszentrum "Tivoli" in Spreitenbach zum Preis von Fr. 22'500'000.-- an ihre zu 100% beherrschte Tochtergesellschaft "XZ._ AG", welche sie im selben Jahr erworben hatte. Aufgrund dieses Verkaufs resultierte in der Erfolgsrechnung der Beschwerdeführerin 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 Beschwerdeführerin 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 Beschwerdeführerin 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 Beschwerdegegnerin mit Blick auf die geplante Veräusserung der genannten Liegenschaften an die Tochtergesellschaft "XZ._ 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 Beschwerdegegnerin im Nachhinein eingesteht - um eine Fehleinschätzung. Entsprechend der bundesgerichtlichen Rechtsprechung liess die Steuerverwaltung bei der Beschwerdeführerin 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 Beschwerdegegnerin riet der Beschwerdeführerin, diese Veranlagung zu akzeptieren. Gemäss provisorischer Steuerrechnung 2001 vom 31. Januar 2003 hatte die Beschwerdeführerin 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 Beschwerdeführerin 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 Beschwerdeführerin im Kanton Genf einen um Fr. 21'244.-- zu hoch ausgefallenen Betrag als Liegenschaftssteuer entrichten, weil die Beschwerdegegnerin 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 Beschwerdeführerin weitergeleitet, als kein Rechtsmittel mehr erhoben werden konnte. Ihren Schadenersatzanspruch trat die Tochtergesellschaft in der Folge an die Beschwerdeführerin ab. B. B.a Am 7. September 2004 reichte die Beschwerdeführerin beim Handelsgericht des Kantons Zürich Klage ein mit dem Begehren, die Beschwerdegegnerin 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 Beschwerdegegnerin 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 Beschwerdeführerin 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 Beschwerdeführerin zur Tragung der Verfahrenskosten (Ziff. 3) und zur Zahlung einer Parteientschädigung (Ziff. 4). C. Mit Beschwerde in Zivilsachen vom 23. März 2009 gegen den Zirkulationsbeschluss des Kassationsgerichts sowie gegen das Urteil des Handelsgerichts beantragt die Beschwerdeführerin dem Bundesgericht, es sei die Beschwerdegegnerin 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. Insoweit das Handelsgericht die Klage guthiess, ficht die Beschwerdeführerin das Urteil nicht an. Sinngemäss verlangt 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. Die Beschwerdegegnerin schliesst in ihrer Vernehmlassung auf Abweisung der Beschwerde. Das Handelsgericht des Kantons Zürich und das Kassationsgericht des Kantons Zürich haben auf eine Vernehmlassung verzichtet. 