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.