Sachverhalt:
A. A.a Club Atlético de Madrid SAD (Beschwerdeführerin) ist ein spanischer Fussballclub mit Sitz in Madrid.
Sport Lisboa E Benfica - Futebol SAD (Beschwerdegegnerin) ist ein portugiesischer Fussballclub mit Sitz in Lissabon.
Beide sind Mitglieder ihrer jeweiligen Nationalverbände, die wiederum der Fédération Internationale de Football Association (FIFA; Verfahrensbeteiligte) angehören, einem Verein schweizerischen Rechts mit Sitz in Zürich.
A.b Anfang September 2000 übernahm die Beschwerdegegnerin vom holländischen Fussballclub AFC Ajax NV den portugiesischen Fussballspieler X._. Der entsprechende Arbeitsvertrag wurde am 13. September 2000 unterzeichnet und sah eine Vertragsdauer von vier Sportsaisons vor. Die Vertragsparteien zerstritten sich bereits kurz darauf und der Fussballspieler X._ kündigte das Arbeitsverhältnis am 6. Dezember 2000 fristlos.
Am 19. Dezember 2000 schloss X._ einen neuen Arbeitsvertrag mit der Beschwerdeführerin ab.
Die von X._ sowie der Beschwerdegegnerin beim zuständigen Arbeitsgericht in Lissabon gegeneinander eingereichten Klagen wurden am 9. Januar 2003 vergleichsweise erledigt.
B. B.a Am 1. Juni 2001 machte die Beschwerdegegnerin bei der FIFA eine Ausbildungs- und Förderungsentschädigung im Sinne von Art. 14.1 des zu jenem Zeitpunkt einschlägigen FIFA-Reglements bezüglich Status und Transfer von Spielern ("Regulations for the Status and Transfer of Players", Ausgabe Oktober 1997; nachfolgend: FIFA-Transferreglement 1997) gegen die Beschwerdeführerin geltend.
Am 26. April 2002 sprach das Special Committee der FIFA der Beschwerdegegnerin eine Entschädigung von USD 2,5 Mio. für die Ausbildung sowie die Förderung des Spielers X._ zu.
Im Juni 2002 focht die Beschwerdeführerin den Entscheid des FIFA-Special Committee vom 26. April 2002 beim Handelsgericht des Kantons Zürich an. Dieses erklärte den Entscheid des FIFA-Special Committee mit Urteil vom 21. Juni 2004 für nichtig. Es erwog, dass das FIFA-Transferreglement 1997 unter anderem gegen das europäische sowie das schweizerische Wettbewerbsrecht verstosse und daher nichtig sei, weshalb auch der darauf gestützte Entscheid des FIFA-Special Committee nichtig sei. Gegen den Entscheid des Handelsgerichts wurde kein Rechtsmittel ergriffen. Die Beschwerdegegnerin war am Anfechtungsprozess nicht beteiligt.
Im Nachgang zum Entscheid des Handelsgerichts schloss die Beschwerdeführerin am 25. August 2004 mit der FIFA eine Vereinbarung ab, mit der sich die FIFA verpflichtete, den Entscheid des Handelsgerichts des Kantons Zürich vom 21. Juni 2004 zu berücksichtigen, falls die Beschwerdegegnerin bei der FIFA erneut Ansprüche in derselben Angelegenheit gegen die Beschwerdeführerin geltend machen sollte.
B.b Am 21. Oktober 2004 ersuchte die Beschwerdegegnerin bei der FIFA erneut um einen Entscheid über die Entschädigung für die Ausbildung und/oder Förderung des Spielers X._ mit dem Antrag, die Beschwerdeführerin sei zur Zahlung von EUR 3'165'928.-- zu verpflichten.
Das Special Committee der FIFA wies das Begehren der Beschwerdegegnerin mit Entscheid vom 14. Februar 2008 (mitgeteilt am 23. Dezember 2008) ab.
B.c Am 13. Januar 2009 appellierte die Beschwerdegegnerin beim Tribunal Arbitral du Sport (TAS) gegen den Entscheid des FIFA-Special Committee vom 14. Februar 2008 und verlangte dessen Aufhebung sowie die Zusprechung von EUR 3'165'928.93 plus Zins oder eines höheren vom Schiedsgericht zu bestimmenden Betrags, eventualiter die Rückweisung an das FIFA-Special Committee zur Neubeurteilung.
Die Beschwerdeführerin widersetzte sich der Berufung und berief sich unter anderem auf die res iudicata-Wirkung des Urteils des Handelsgerichts Zürich vom 21. Juni 2004.
Mit Schiedsentscheid vom 31. August 2009 hiess das TAS die Berufung der Beschwerdegegnerin teilweise gut und verpflichtete die Beschwerdeführerin gestützt auf das FIFA-Transferreglement 1997, der Beschwerdegegnerin den Betrag von EUR 400'000.-- zu bezahlen.
C. Mit Beschwerde in Zivilsachen beantragt die Beschwerdeführerin dem Bundesgericht in erster Linie die Aufhebung des Schiedsentscheids des TAS vom 31. August 2009.
Die Beschwerdegegnerin sowie das TAS beantragen die Abweisung der Beschwerde. Die FIFA hat auf eine aktive Beteiligung am Verfahren verzichtet.
D. Mit Verfügung vom 24. Februar 2010 wies das Bundesgericht das Gesuch der Beschwerdeführerin um Erlass eines Zwischenentscheids zur Frage der Rechtzeitigkeit der Beschwerdeantwort sowie das sinngemässe Gesuch um Ansetzung einer Frist zur Einreichung einer Replikschrift ab. Im Übrigen wies es die Beschwerdeführerin darauf hin, dass Verzicht auf die Einreichung einer Replik angenommen werde, sofern sie die Replikschrift nicht innerhalb weniger Tag nach Zustellung der Verfügung beim Bundesgericht einreiche.
Die Beschwerdeführerin verzichtete in der Folge auf die Einreichung einer Replikschrift.

Erwägungen:
1. Die Beschwerde in Zivilsachen ist gegen Entscheide von Schiedsgerichten unter den Voraussetzungen der Art. 190-192 IPRG zulässig (<ref-law>).
1.1 Der Sitz des Schiedsgerichts befindet sich vorliegend in Lausanne. Sowohl die Beschwerdeführerin als auch die Beschwerdegegnerin hatten im relevanten Zeitpunkt ihren Sitz ausserhalb der Schweiz. Da die Parteien die Bestimmungen des 12. Kapitels des IPRG nicht schriftlich ausgeschlossen haben, gelangen diese zur Anwendung (Art. 176 Abs. 1 und 2 IPRG).
Das TAS hat nebst den einschlägigen Bestimmungen der FIFA-Reglemente schweizerisches Recht für anwendbar erklärt. Die Parteien stellen die Anwendbarkeit des schweizerischen Rechts nicht in Frage. Sie waren sich im Schiedsverfahren zudem einig, dass grundsätzlich das FIFA-Transferreglement 1997 auf die strittige Frage anwendbar sei.
1.2 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. 3b S. 382).
1.3 Die Frage, ob die Beschwerdegegnerin ihr Gesuch um Fristerstreckung zur Einreichung der Beschwerdeantwort rechtzeitig gestellt hat und ihre Antwort damit fristgerecht beim Bundesgericht eingegangen ist, braucht nicht vertieft zu werden, da sich die Beschwerde auch bei Berücksichtigung der Antwort als begründet erweist.
2. Die Beschwerdeführerin wirft der Vorinstanz eine Verletzung des Ordre public (<ref-law>) vor, da sie die materielle Rechtskraft des Urteils des Handelsgerichts des Kantons Zürich vom 21. Juni 2004 in der gleichen Sache nicht beachtet habe.
2.1 Der Ordre public (<ref-law>) hat sowohl einen materiellen als auch einen verfahrensrechtlichen Gehalt.
Ein Verstoss gegen den verfahrensrechtlichen Ordre public liegt vor bei einer Verletzung von fundamentalen und allgemein anerkannten Verfahrensgrundsätzen, deren Nichtbeachtung zum Rechtsempfinden in einem unerträglichen Widerspruch steht, so dass die Entscheidung als mit der in einem Rechtsstaat geltenden Rechts- und Wertordnung schlechterdings unvereinbar erscheint (<ref-ruling> E. 2.2.1 S. 392; <ref-ruling> E. 4a S. 194; <ref-ruling> E. 3b S. 253 mit Hinweisen).
Das Schiedsgericht verletzt den verfahrensrechtlichen Ordre public, wenn es bei seinem Entscheid die materielle Rechtskraft eines früheren Entscheids unbeachtet lässt oder wenn es in seinem Endentscheid von der Auffassung abweicht, die es in einem Vorentscheid hinsichtlich einer materiellen Vorfrage geäussert hat (BGE <ref-ruling> E. 4a S. 194 mit Hinweisen; vgl. auch BGE <ref-ruling> E. 2b S. 283).
Die Rechtskraftwirkung beschränkt sich auf das Urteilsdispositiv. Die Urteilsbegründung wird davon nicht erfasst. Die Urteilserwägungen haben in einer anderen Streitsache keine bindende Wirkung, sind aber gegebenenfalls zur Klärung der Tragweite des Urteilsdispositivs beizuziehen (BGE <ref-ruling> E. 4a S. 195; <ref-ruling> E. 3b S. 13; <ref-ruling> E. 2a S. 18 f.). Die Tragweite des konkreten Urteilsdispositivs ist demnach im Einzelfall anhand der gesamten Urteilserwägungen zu beurteilen.
2.2 Das TAS hat den Einwand der res iudicata im schiedsgerichtlichen Verfahren zu Unrecht verworfen.
2.2.1 Das TAS hat zu Unrecht darauf abgestellt, dass es sich beim Verfahren vor dem Handelsgericht des Kantons Zürich nicht um eine Berufung gegen einen Entscheid der FIFA gehandelt habe, wie diejenige an das TAS, sondern um eine Anfechtung eines vereinsrechtlichen Beschlusses nach <ref-law>. Entgegen dem angefochtenen Schiedsentscheid ist es für die Beurteilung der Rechtskraftwirkung des Urteils des Handelsgerichts vom 21. Juni 2004 unerheblich, dass es sich beim entsprechenden Verfahren nicht um ein Schiedsverfahren handelte, sondern um ein "unabhängiges innerstaatliches Anfechtungsverfahren" ("an independent Swiss domestic procedure aiming to contest a decision rendered by a Swiss law association") nach <ref-law> (vgl. BGE <ref-ruling> E. 2c/bb S. 284). Wie die Beschwerdeführerin zu Recht vorbringt und von der Beschwerdegegnerin nicht in Abrede gestellt wird, war es ihr nach Erhalt der ursprünglichen Entscheidung des FIFA-Special Committee vom 26. April 2002 nicht etwa mangels Schiedsfähigkeit verwehrt, ein Schiedsgericht zur Anfechtung des Entscheids anzurufen, sondern weil damals eine Überprüfung von Vereinsbeschlüssen durch das TAS nach den FIFA-Statuten noch nicht vorgesehen war. Entsprechend war der FIFA-Entscheid bei einem staatlichen Gericht nach <ref-law> anzufechten.
Der Umstand, dass die zweite Entscheidung des FIFA-Special Committee vom 14. Februar 2008 aufgrund einer Schiedsklausel in den FIFA-Statuten beim TAS angefochten werden konnte, ändert entgegen der Ansicht der Beschwerdegegnerin nichts daran, dass es in diesem Verfahren einmal mehr um den Vereinsbeschluss über den von der Beschwerdegegnerin geltend gemachten Anspruch gegen die Beschwerdeführerin auf Zusprechung einer Ausbildungs- und Förderungsentschädigung für den Spieler X._ ging. Beim Verfahren vor dem TAS, in dem sich die Beschwerdegegnerin gegen die von der FIFA verweigerte Zusprechung der verlangten Entschädigungszahlung wehrt, handelt es sich letztlich um nichts anderes als eine schiedsgerichtliche Beurteilung der Anfechtung eines von einem schweizerischen Verein gefassten Beschlusses (vgl. etwa Urs Scherrer, Aktuelle Rechtsfragen bei Sportvereinen, in: Riemer [Hrsg.], Aktuelle Fragen aus dem Vereinsrecht, 2005, S. 60 f.; Heini/Portmann, Das Schweizerische Vereinsrecht, in: Schweizerisches Privatrecht, Bd. II/5, 3. Aufl. 2005, Rz. 285). Das TAS verweist hinsichtlich der Zuständigkeit denn auch auf Art. R47 des TAS-Code, der die Berufung ("Appeal") unter anderem gegen Entscheide eines Verbands regelt (vgl. die Überschrift "Special Provisions Applicable to the Appeal Arbitration Procedure"), und nicht auf Art. R38 ff. TAS-Code über das ordentliche Schiedsverfahren ("Ordinary Arbitration Procedure", vgl. Art. R38 ff. TAS-Code), das einen Rechtsstreit unabhängig von einem Entscheid eines Verbands zum Gegenstand hat (vgl. Art. R27 TAS-Code).
2.2.2 In den beiden Verfahren vor dem Handelsgericht des Kantons Zürich sowie dem TAS war jeweils die Rechtmässigkeit der Entscheidung des FIFA-Special Committee über die von der Beschwerdegegnerin gegenüber der Beschwerdeführerin geltend gemachte Ausbildungs- und Förderungsentschädigung für den Spieler X._ zu beurteilen. Das Handelsgericht erklärte den auf das FIFA-Transferreglement 1997 gestützten ersten Entscheid des FIFA-Special Committee mit Urteil vom 21. Juni 2004 für nichtig, da er auf einem Transferreglement beruhe, das unter anderem wegen Verletzung des europäischen sowie des schweizerischen Wettbewerbsrechts nichtig sei. Trotz grundsätzlich kassatorischer Natur der in <ref-law> vorgesehenen Anfechtungsklage ist das zuständige Vereinsorgan an die Erwägungen des Urteils, mit dem der angefochtene Vereinsbeschluss aufgehoben wird, gebunden (<ref-ruling> E. 1c S. 14 mit Verweis auf Riemer, Berner Kommentar, 3. Aufl. 1990, N. 82 zu <ref-law>). Umso mehr hatte das FIFA-Special Committee das handelsgerichtliche Urteil zu beachten, mit dem sein Entscheid wegen nichtiger Rechtsgrundlage nicht bloss aufgehoben, sondern für nichtig erklärt wurde (vgl. Riemer, a.a.O., N. 129 f. zu <ref-law>), und es konnte nicht angehen, der Beschwerdegegnerin in einem neuerlichen Entscheid gestützt auf dasselbe FIFA-Transferreglement 1997 dennoch eine Ausbildungs- und Förderungsentschädigung für den Spieler X._ zuzusprechen.
Entsprechend wies das FIFA-Special Committee das erneute Begehren der Beschwerdegegnerin, es sei ihr zu Lasten der Beschwerdeführerin eine Entschädigung für die Ausbildung und/oder Förderung des Spielers X._ zuzusprechen, mit Entscheid vom 14. Februar 2008 im Ergebnis folgerichtig ab. Das daraufhin angerufene TAS auferlegte der Beschwerdeführerin demgegenüber gestützt auf Art. 14 des FIFA-Transferreglements 1997 eine Entschädigung von EUR 400'000.--, wobei es deren Höhe in hilfsweiser Anwendung von <ref-law> festsetzte. Damit setzte es sich über das Urteil des Handelsgerichts des Kantons Zürich vom 21. Juni 2004 hinweg, das die Verpflichtung der Beschwerdeführerin zur Zahlung einer Ausbildungs- und Förderungsentschädigung gestützt auf das FIFA-Transferreglement 1997 durch das FIFA-Special Committee für nichtig erklärte.
Daran vermag auch der unter Berufung auf den Gehörsanspruch erhobene Einwand der Beschwerdegegnerin nichts zu ändern, sie sei im Verfahren vor Handelsgericht nicht Partei gewesen und habe daran auch sonst in keiner Weise teilgenommen. Die Parteirollen vor Handelsgericht ergaben sich folgerichtig aus <ref-law>, da bei der Anfechtungsklage immer nur der Verein, und nicht etwa ein anderes am Beschluss interessiertes Mitglied passivlegitimiert ist (Riemer, a.a.O., N. 60 zu <ref-law>; vgl. <ref-ruling> E. 3.1 S. 507). Abgesehen davon wirkt die Gutheissung der Klage auf Nichtigerklärung eines Vereinsbeschlusses wie auch der Anfechtungsklage - im Gegensatz zu deren Abweisung - nicht bloss zwischen den Verfahrensparteien, sondern erga omnes (Riemer, Anfechtungs- und Nichtigkeitsklage im schweizerischen Gesellschaftsrecht [AG, GmbH, Genossenschaft, Verein, Stockwerkeigentümergemeinschaft], 1998, Rz. 304, 218; derselbe, a.a.O., N. 81 zu <ref-law>; Heini/Scherrer, in: Basler Kommentar, Zivilgesetzbuch I, 3. Aufl. 2006, N. 31 und 38 zu <ref-law>; vgl. auch Henk Fenners, Der Ausschluss der staatlichen Gerichtsbarkeit im organisierten Sport, 2006, S. 75 Rz. 253; <ref-ruling> E. 3c/bb S. 284 f. sowie <ref-law>).
Dass die FIFA nachträglich ein Schiedsverfahren zur Anfechtung ihrer Beschlüsse einführte, an dem die Beschwerdegegnerin nunmehr als Partei teilnimmt und das es dem TAS erlaubt, den Fall von Grund auf neu zu entscheiden (Art. R57 TAS-Code), ändert nichts an der Tatsache, dass die vom TAS zu beurteilende Frage der Rechtmässigkeit der vom FIFA-Special Committee festgesetzten bzw. verweigerten Entschädigung zwischen der Beschwerdegegnerin und der Beschwerdeführerin für die Ausbildung und/oder Förderung des Spielers X._ bereits mit handelsgerichtlichem Urteil vom 21. Juni 2004 entschieden worden war, das in Rechtskraft erwachsen ist. Die nachträgliche Einführung einer schiedsgerichtlichen Anfechtung vereinsrechtlicher Beschlüsse blieb ohne Einfluss auf die materielle Rechtskraft bereits ergangener Anfechtungsentscheide staatlicher Gerichte. Auch im Verhältnis zur neuen Anfechtungsmöglichkeit galt es, widersprechende Urteile über dieselbe Sache in verschiedenen Prozessen zu verhindern (vgl. Max Guldener, Schweizerisches Zivilprozessrecht, 3. Aufl. 1979, S. 364). Wie das Handelsgericht des Kantons Zürich bei einer zweiten Anfechtungsklage gegen einen weiteren FIFA-Entscheid über die Ausbildungs- und Förderungsentschädigung für den Spieler X._ an sein früheres Urteil gebunden gewesen wäre, mit dem es die von der FIFA zugesprochene Entschädigung aufgrund der Nichtigkeit des FIFA-Transferreglements 1997 für nichtig erklärte, durfte auch das später für zuständig erklärte Schiedsgericht die bereits entschiedene Frage nicht erneut prüfen.
2.2.3 Dem Schiedsgericht kann im Übrigen nicht gefolgt werden, wenn es der Beschwerdeführerin sowie der FIFA im Zusammenhang mit der Frage der Rechtskraftwirkung vorhält, sie hätten mit ihrer Vereinbarung vom 25. August 2004 im Nachgang zum Entscheid des Handelsgerichts des Kantons Zürich vorausgesehen, dass bei der FIFA ein neues Begehren in derselben Angelegenheit eingereicht werden könnte. Wenn sich die FIFA gegenüber der Beschwerdeführerin verpflichtete, den Entscheid des Handelsgerichts zu berücksichtigen, falls die Beschwerdegegnerin erneut Ansprüche in derselben Angelegenheit gegen die Beschwerdeführerin geltend machen sollte, so wurde damit entgegen der Ansicht des TAS gerade dessen Geltung für spätere Verfahren bekräftigt. Dass sie mit der Einreichung weiterer Begehren rechneten, bedeutet keineswegs, dass sie sich mit einer erneuten Beurteilung derselben Ansprüche einverstanden erklärten.
2.2.4 Dem Entscheid des TAS über die Ausbildungs- und Förderungsentschädigung für den Spieler X._ stand die res iudicata entgegen. Der Schiedsentscheid, mit dem das TAS der Beschwerdeführerin gestützt auf das FIFA-Transferreglement 1997, in Missachtung der materiellen Rechtskraft des Urteils des Handelsgerichts des Kantons Zürich vom 21. Juni 2004, eine Ausbildungs- und Förderungsentschädigung von EUR 400'000.-- für den Spieler X._ auferlegte, verstösst daher gegen den verfahrensrechtlichen Ordre public.
3. Die Beschwerde ist gutzuheissen und der Entscheid des TAS vom 31. August 2009 ist aufzuheben. Dem Ausgang des Verfahrens entsprechend wird die Beschwerdegegnerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 sowie Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid der Vorinstanz vom 31. August 2009 wird aufgehoben.
2. Die Gerichtskosten von Fr. 8'500.-- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat die Beschwerdeführerin für das bundesgerichtliche Verfahren mit Fr. 9'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Verfahrensbeteiligten und dem Tribunal Arbitral du Sport (TAS) schriftlich mitgeteilt.
Lausanne, 13. April 2010
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Der Gerichtsschreiber:
Klett Leemann