Sachverhalt:
A. A.a Die X._ SpA mit Sitz in K._, Italien, (Beklagte, Beschwerdeführerin) ist ein privat gehaltenes Flugunternehmen.
Die Y._ GmbH, L._, Deutschland, (Klägerin, Beschwerdegegnerin) ist ein im Fluggeschäft tätiges Beratungsunternehmen.
A.b Die Parteien schlossen am 29. Oktober 2010 einen als "Consultancy Agreement" bezeichneten Vertrag ab, der eine Schiedsklausel und eine Wahl zugunsten des schweizerischen Rechts enthält. Der Vertrag sieht vor, dass die Y._ GmbH die X._ SpA im Hinblick auf mögliche Kosteneinsparungen beim technischen Unterhalt berät, unter anderem durch Beurteilung der bestehenden Wartungsverträge sowie Unterstützung bei der Verhandlung über deren Verlängerung oder den Abschluss neuer Verträge.
Die X._ SpA konnte am 6. Juni 2011 als Ergebnis der Bemühungen der Y._ GmbH einen neuen Vertrag mit der Z._ AG abschliessen, der den bestehenden Wartungsvertrag mit W._ ersetzte. Zwischen den Parteien blieb in der Folge strittig, ob sich daraus ein Anspruch der Y._ GmbH auf ein Erfolgshonorar ergibt.
B. Die Y._ GmbH leitete am 11. August 2011 bei der Zürcher Handelskammer ein Schiedsverfahren ein mit dem (im Laufe des Verfahrens ergänzten) Rechtsbegehren, die X._ SpA sei zur Zahlung von EUR 435'150.--, zuzüglich 5 % Zins seit dem 11. Juli 2011, zu verurteilen. Diese beantragte die Abweisung der Schiedsklage.
Am 18. November 2011 ernannten die Parteien gemeinsam einen Einzelschiedsrichter, der in der Folge von der Zürcher Handelskammer bestätigt wurde.
Nach Durchführung einer dreitägigen mündlichen Verhandlung hiess der Einzelschiedsrichter die Schiedsklage mit Entscheid vom 20. Juli 2012 gut (Dispositiv-Ziffer 1), setzte die Verfahrenskosten fest (Dispositiv-Ziffern 2 und 3), auferlegte der Beklagten die Kosten sowie eine Parteientschädigung (Dispositiv-Ziffern 4 und 5) und regelte den Zinsenlauf (Dispositiv-Ziffer 6); alle weiteren Anträge wies der Einzelschiedsrichter ab (Dispositiv-Ziffer 7).
C. Mit Beschwerde in Zivilsachen beantragt die Beklagte dem Bundesgericht, es sei der Schiedsentscheid vom 20. Juli 2012 "in Ziff. 1, 4, 5 und 6 des Dispositivs aufzuheben und es sei die Angelegenheit zur Neubeurteilung an den Einzelschiedsrichter zurückzuweisen, wobei dieser anzuweisen sei, im Sinne der Erwägungen des Bundesgerichts die Klage der Beschwerdegegnerin vollumfänglich abzuweisen". Eventualiter sei der angefochtene Schiedsentscheid in den erwähnten Dispositiv-Ziffern aufzuheben und die Sache an den Einzelschiedsrichter zurückzuweisen.
Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde. Der Einzelschiedsrichter hat auf eine Vernehmlassung verzichtet.
Die Beschwerdeführerin hat dem Bundesgericht am 4. Januar 2013 eine Replik, die Beschwerdegegnerin am 11. Januar 2013 eine Duplik eingereicht.
D. Mit Verfügung vom 3. Dezember 2012 entfernte das Bundesgericht ein von der Beschwerdegegnerin eingereichtes Beweismittel auf ihr Ersuchen hin aus den Akten und wies das Gesuch der Beschwerdeführerin um Gewährung der aufschiebenden Wirkung ab.

Erwägungen:
1. Nach <ref-law> ergeht der Entscheid des Bundesgerichts in einer Amtssprache, in der Regel in jener des angefochtenen Entscheids. Wurde dieser in einer anderen Sprache redigiert, verwendet das Bundesgericht die von den Parteien gewählte Amtssprache. Der angefochtene Entscheid ist in englischer Sprache abgefasst. Da es sich dabei nicht um eine Amtssprache handelt und sich die Parteien vor Bundesgericht der deutschen Sprache bedienen, ergeht der Entscheid des Bundesgerichts auf Deutsch.
2. Im Bereich der internationalen Schiedsgerichtsbarkeit ist die Beschwerde in Zivilsachen unter den Voraussetzungen der Art. 190-192 IPRG (SR 291) zulässig (<ref-law>).
2.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Zürich. Die Parteien hatten im relevanten Zeitpunkt ihren Sitz ausserhalb der Schweiz. Da sie die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
2.2 Die Beschwerde in Zivilsachen im Sinne von <ref-law> ist grundsätzlich rein kassatorischer Natur, d.h. sie kann nur zur Aufhebung des angefochtenen Entscheids führen (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> ausschliesst, soweit dieser dem Bundesgericht erlaubt, in der Sache selbst zu entscheiden). Soweit der Streit die Zuständigkeit des Schiedsgerichts betrifft, gilt davon allerdings eine dahingehende Ausnahme, dass das Bundesgericht selber die Zuständigkeit oder die Unzuständigkeit des Schiedsgerichts feststellen kann (<ref-ruling> E. 3.3.4 S. 616 mit Hinweisen).
Unzulässig ist der von der Beschwerdeführerin über die Aufhebung von Dispositiv-Ziffern 1, 4, 5 und 6 hinaus gestellte Antrag, der Einzelschiedsrichter sei anzuweisen, im Sinne der Erwägungen des Bundesgerichts die Klage der Beschwerdegegnerin abzuweisen. Soweit die Beschwerdeführerin vom Bundesgericht einen materiellen Entscheid bzw. eine konkrete Anweisung an das Schiedsgericht über die zu treffende Entscheidung begehrt, ist auf den Antrag nicht einzutreten.
2.3 Zulässig sind allein die Rügen, die in <ref-law> abschliessend aufgezählt sind (<ref-ruling> E. 5 S. 187; <ref-ruling> E. 1a S. 53; <ref-ruling> E. 1a S. 282). Nach <ref-law> prüft das Bundesgericht nur die Rügen, die in der Beschwerde vorgebracht und begründet worden sind; dies entspricht der in <ref-law> für die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht vorgesehenen Rügepflicht (<ref-ruling> E. 5 S. 187 mit Hinweis). Appellatorische Kritik ist unzulässig (<ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 3b S. 382).
2.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den das Schiedsgericht festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung des Schiedsgerichts weder berichtigen noch ergänzen, selbst wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (vgl. <ref-law>, der die Anwendbarkeit von <ref-law> sowie <ref-law> ausschliesst). Allerdings kann das Bundesgericht die tatsächlichen Feststellungen des angefochtenen Schiedsentscheids überprüfen, wenn gegenüber diesen Sachverhaltsfeststellungen zulässige Rügen im Sinne von <ref-law> vorgebracht oder ausnahmsweise Noven berücksichtigt werden (<ref-ruling> E. 2.2.1 S. 34; <ref-ruling> E. 3.1 S. 567; <ref-ruling> E. 5 S. 141; je mit Hinweisen). Wer sich auf eine Ausnahme von der Bindung des Bundesgerichts an die tatsächlichen Feststellungen der Vorinstanz beruft und den Sachverhalt gestützt darauf berichtigt oder ergänzt wissen will, hat mit Aktenhinweisen darzulegen, dass entsprechende Sachbehauptungen bereits im vorinstanzlichen Verfahren prozesskonform aufgestellt worden sind (vgl. <ref-ruling> E. 2a S. 486; <ref-ruling> E. 1c S. 473; je mit Hinweisen).
3. Die Beschwerdeführerin rügt, der angefochtene Entscheid sei mit dem Ordre public unvereinbar (<ref-law>).
3.1 Sie bringt vor, die schiedsgerichtliche Erwägung, wonach sie sich im konkreten Fall nicht auf Grundlagenirrtum berufen könne, sei mit den hiesigen Wertvorstellungen offensichtlich unvereinbar. Nach einem allgemeinen Rechtsgrundsatz sei ein Vertrag für denjenigen unverbindlich, der sich beim Abschluss in einem wesentlichen Irrtum befunden habe. Dies treffe vorliegend zu, da der Irrtum ein Sachverhaltselement betroffen habe, das vom Irrenden nach Treu und Glauben im Geschäftsverkehr als eine notwendige Grundlage des Vertrags habe betrachtet werden dürfen. Der Einzelschiedsrichter habe diesen Grundsatz zu beachten und verletzte den Ordre public, wenn er bei Vorliegen der Voraussetzungen eines Grundlagenirrtums den Vertrag als gültig erachte. Diese Voraussetzungen habe sie in ihren Rechtsschriften einzeln dargelegt und mit ihren Ausführungen bewiesen, dass der Beratungsvertrag ungültig und das vereinbarte Erfolgshonorar damit nicht geschuldet sei. Indem der Einzelschiedsrichter den Beratungsvertrag trotz Vorliegens sämtlicher Voraussetzungen eines Grundlagenirrtums als gültig erklärte, habe er das Vertrauensprinzip verletzt.
3.2 Die materiellrechtliche Überprüfung eines internationalen Schiedsentscheids durch das Bundesgericht ist auf die Frage beschränkt, ob der Schiedsspruch mit dem Ordre public vereinbar ist (<ref-ruling> E. 3a S. 333). Gegen den Ordre public verstösst die materielle Beurteilung eines streitigen Anspruchs nur, wenn sie fundamentale Rechtsgrundsätze verkennt und daher mit der wesentlichen, weitgehend anerkannten Wertordnung schlechthin unvereinbar ist, die nach in der Schweiz herrschender Auffassung Grundlage jeder Rechtsordnung bilden sollte. Zu diesen Grundsätzen gehören die Vertragstreue (pacta sunt servanda), das Rechtsmissbrauchsverbot, der Grundsatz von Treu und Glauben, das Verbot der entschädigungslosen Enteignung, das Diskriminierungsverbot, der Schutz von Handlungsunfähigen und das Verbot übermässiger Bindung (vgl. <ref-law>), wenn diese eine offensichtliche und schwerwiegende Persönlichkeitsverletzung darstellt. Zur Aufhebung des angefochtenen Schiedsentscheids kommt es nur, wenn dieser nicht nur in der Begründung, sondern auch im Ergebnis dem Ordre public widerspricht (<ref-ruling> E. 4.1 sowie E. 4.3.1/4.3.2; <ref-ruling> E. 2.2 S. 392 ff.; je mit Hinweisen).
Entgegen der in der Beschwerde vertretenen Ansicht hat der Einzelschiedsrichter nicht verkannt, dass der Grundsatz von Treu und Glauben zu beachten ist; ebenso wenig hat er grundsätzlich in Frage gestellt, dass die Vereinbarung von einer Vertragspartei infolge Grundlagenirrtums für ungültig erklärt werden kann. Er hat den Einwand der Beschwerdeführerin, sie habe sich bei Abschluss der Vereinbarung vom 29. Oktober 2010 in einem Grundlagenirrtum befunden, vielmehr anhand des anwendbaren schweizerischen Rechts (<ref-law>) geprüft, jedoch gestützt auf <ref-law> dafürgehalten, sie habe von der Verbindung zwischen der Beschwerdegegnerin und Z._ AG gewusst und hätte die erforderlichen Abklärungen treffen müssen, falls die später beanstandete Zusammenarbeit für sie von Bedeutung gewesen wäre. <ref-law> sieht gerade vor, dass die Berufung auf Irrtum unstatthaft ist, wenn sie Treu und Glauben widerspricht. Davon, dass der Einzelschiedsrichter diesen Grundsatz in Missachtung des Ordre public unbeachtet gelassen hätte, kann keine Rede sein.
Soweit die Beschwerdeführerin dem Bundesgericht unter Hinweis auf ihre Rechtsschriften im Schiedsverfahren ihre verschiedenen Vorbringen zu den Voraussetzungen des Grundlagenirrtums unterbreitet und daraus ableiten will, der von ihr behauptete Irrtum sei entgegen dem angefochtenen Entscheid beachtlich und der Beratungsvertrag vom 29. Oktober 2010 ungültig, kritisiert sie lediglich in appellatorischer Weise die massgeblichen Erwägungen im angefochtenen Entscheid. Eine Verletzung des Ordre public (<ref-law>) zeigt sie mit ihren Ausführungen nicht auf.
3.3 Auch mit ihrem eventualiter erhobenen Vorbringen, der Einzelschiedsrichter habe zu Unrecht erwogen, dass der Beratungsvertrag vom 29. Oktober 2010 nicht als Mäklervertrag in Sinne von <ref-law> zu qualifizieren sei und die Anwendung von <ref-law> ausser Betracht falle, zeigt die Beschwerdeführerin keine Missachtung des Ordre public auf, sondern unterbreitet dem Bundesgericht unter Hinweis auf verschiedene Eingaben ihre Ausführungen zu ihrem im Schiedsverfahren erhobenen Einwand, die Beschwerdegegnerin habe ihren Honoraranspruch verwirkt, als ob das Bundesgericht im Beschwerdeverfahren die Streitsache von Grund auf neu überprüfen könnte. Damit verkennt sie den Begriff des Ordre public und die eingeschränkte Prüfungsbefugnis des Bundesgerichts im Rahmen der Beschwerde gegen einen internationalen Schiedsentscheid. Im Umstand, dass der Einzelschiedsrichter den Beratungsvertrag vom 29. Oktober 2010 entgegen der Rechtsauffassung der Beschwerdeführerin nicht als Maklervertrag betrachtete und eine Anwendung von <ref-law> ablehnte, ist keine Missachtung des Ordre public (<ref-law>) zu erblicken.
4. Die Beschwerdeführerin wirft dem Schiedsgericht eine Verletzung des rechtlichen Gehörs (<ref-law>) vor.
4.1 Sie macht geltend, der Einzelschiedsrichter sei zu Unrecht zur Auffassung gelangt, sie könne sich nicht auf Grundlagenirrtum (<ref-law>) berufen, da sie es unterlassen habe darzulegen, wann und wie sie die behauptete Treuepflichtverletzungen der Beschwerdegegnerin entdeckt habe. Die schiedsgerichtliche Feststellung hinsichtlich ihrer Parteivorbringen beruhe auf einem Versehen und verletze ihr rechtliches Gehör, habe sie doch in ihrer Eingabe nach der mündlichen Verhandlung (Post Hearing Brief) unter anderem ausdrücklich darauf hingewiesen, dass sie von der Doppelvertretung durch die Beschwerdegegnerin erst anlässlich der Befragung von Herrn B._ am 22. Mai 2012 Kenntnis erhalten habe.
4.2 Der Einzelschiedsrichter hat seine Erwägung, wonach sich die Beschwerdeführerin nicht auf einen Grundlagenirrtum nach Art. 23 in Verbindung mit <ref-law> berufen könne, auf zwei selbständige Begründungen gestützt: Einerseits habe sie es unterlassen, im Schiedsverfahren darzulegen, wann und wie sie die behaupteten Treuepflichtverletzungen der Gegenpartei entdeckt habe, weshalb er auch nicht überprüfen könne, ob die Beschwerdeführerin die Erklärung nach <ref-law> fristgerecht abgegeben habe. Andererseits hielt der Einzelschiedsrichter gestützt auf <ref-law> dafür, die Beschwerdeführerin habe von der Verbindung der Beschwerdegegnerin mit der Z._ AG bereits vor Abschluss des Vertrags mit Letzterer Kenntnis gehabt und hätte daher die erforderlichen Abklärungen vornehmen müssen, falls diese Zusammenarbeit für sie von Bedeutung gewesen wäre.
Der Einzelschiedsrichter hat somit den Einwand des Grundlagenirrtums gestützt auf <ref-law> unabhängig von der Frage der Rechtzeitigkeit der Erklärung der Beschwerdeführerin (vgl. <ref-law>) verworfen. Wie sich erwiesen hat, ist diese Begründung, die den angefochtenen Entscheid selbständig stützt, nicht zu beanstanden (vgl. vorne E. 3.2). Es erübrigt sich daher auf die Gehörsrüge einzugehen, die sich lediglich gegen eine weitere selbständige Begründung des Einzelschiedsrichters richtet.
5. Die Beschwerde erweist sich als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 8'000.-- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 9'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Schiedsgericht der Zürcher Handelskammer schriftlich mitgeteilt.
Lausanne, 18. April 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Leemann