Sachverhalt: A. A.a X._ (Beschwerdeführer) ist ein deutscher Verein mit Sitz in D._, der dem Deutschen Fussball-Bund angehört. Y._ (Beschwerdegegner) ist der nationale Fussballverband von F._ und gehört der Fédération Internationale de Football Association (FIFA) an. A.b Am 7. Juli 2008 teilte der Beschwerdegegner dem Deutschen Fussball-Bund mit, dass unter anderem der Spieler Z._ "Z._" (nachfolgend Z._), der damals beim Beschwerdeführer spielte und weniger als 23 Jahre alt war, von der Nationalmannschaft von F._ zur Teilnahme an den Olympischen Spielen in Peking im August 2008 selektioniert worden sei. Der Beschwerdegegner bat den deutschen Nationalverband, den Beschwerdeführer anzuweisen, den Spieler für diesen Anlass freizustellen. Mit Schreiben vom 11. Juli 2008 lehnte der Beschwerdeführer dieses Ersuchen ab und stellte sich auf den Standpunkt, dass nach dem anwendbaren FIFA-Reglement keine Verpflichtung für die Freigabe von Z._ bestehe. Ebenfalls am 11. Juli 2008 ersuchte der Beschwerdegegner den Deutschen Fussball-Bund erneut, den Beschwerdeführer über seine Verpflichtung zur Freigabe des Spielers zu informieren. Der Deutsche Fussball-Bund antwortete am 17. Juli 2008, wobei er sich der Rechtsauffassung des Beschwerdeführers anschloss und eine Verpflichtung zur Freigabe verneinte. Am gleichen Tag teilte der Beschwerdegegner dem Beschwerdeführer den Flugplan des Spielers im Hinblick auf die Zusammenkunft der F._ Nationalmannschaft für die Olympischen Spiele mit. Nachdem Z._ nicht ins Trainingslager eingerückt war, wies der Rechtsvertreter des Beschwerdeführers den Spieler mit Schreiben vom 21. Juli 2008 darauf hin, dass er seine arbeitsvertraglichen Pflichten gegenüber dem Verein verletze und daher schadenersatzpflichtig werde. Am 22. Juli 2008 reiste Z._ von Deutschland ab, um sich der F._ Nationalmannschaft in Peking anzuschliessen. Am gleichen Tag forderte der Rechtsvertreter des Beschwerdeführers den Beschwerdegegner zur Abgabe einer schriftlichen Erklärung auf, mit der sich Letzterer unter anderem dazu verpflichten sollte, keinen weiteren Druck auf den Spieler auszuüben und kündigte rechtliche Schritte an, sollte die Erklärung nicht bis zum 23. Juli 2008 vorliegen. Am 23. Juli 2008 erging das Rundschreiben 1153 der FIFA, das sich zur Frage der Freistellung von Fussballspielern für die Olympischen Spiele 2008 dahingehend äusserte, dass Spieler unter 23 Jahren für die Spiele in Peking freizustellen seien. Am 29. Juli 2008 sprach sich auch das Emergency Committee der FIFA zugunsten einer solchen Pflicht zur Freistellung aus. Am 6. August 2008 erging ein Entscheid des Tribunal Arbitral du Sport (TAS) betreffend verschiedene Verfahren des Beschwerdeführers sowie weiterer Fussballvereine gegen die FIFA, in dem das TAS unter anderem erwog, dass den Beschwerdeführer keine rechtliche Verpflichtung zur Freistellung des Spielers Z._ für das olympische Fussballturnier 2008 in Peking treffe. Ein Angebot des Beschwerdeführers vom gleichen Tag, den Spieler gegen Bezahlung sowie Gewährleistung einer bestimmten Versicherungsdeckung für die Olympischen Spiele freizustellen, blieb vom Beschwerdegegner unbeantwortet. A.c Am 11. August 2008 erhob der Beschwerdeführer beim FIFA Players' Status Committee Klage gegen den Beschwerdegegner und beantragte im Wesentlichen, der Beschwerdegegner sei dazu zu verpflichten, den Spieler Z._ weder für die Vorbereitungstrainings noch für das olympische Fussballturnier zu engagieren und ihn umgehend zum Beschwerdeführer zurückreisen zu lassen. Zudem sei eine Schadenersatzzahlung von EUR 50'000.-- an die Stiftung "G._" für jeden zusätzlichen Tag ab Urteilsfällung vorzusehen, an dem der Spieler Z._ im Vorbereitungstraining oder im olympischen Fussballturnier eingesetzt werde sowie eine Zahlung von EUR 26'600.-- für jeden Tag ab dem 23. Juli 2008 bis zur Urteilsfällung. Die FIFA teilte dem Beschwerdeführer mit Schreiben vom 12. August 2008, das vom Head of Legal Affairs sowie vom Head of Players' Status unterzeichnet wurde, mit, dass sie sich nicht in der Lage sehe, in dieser Angelegenheit einzuschreiten. B. Der Beschwerdeführer focht das Schreiben der FIFA vom 12. August 2008 noch am gleichen Tag beim TAS an und beantragte, der Entscheid sei aufzuheben und den der FIFA unterbreiteten Begehren sei stattzugeben. Mit ergänzendem Statement of Appeal vom 14. August 2008 passte der Beschwerdeführer unter anderem seine Zahlungsbegehren an, beantragte jedoch weiterhin in erster Linie die Aufhebung des angefochtenen Entscheids. Das TAS entschied mit Schiedsspruch vom 16. Dezember 2008, dass der Appeal bezüglich des Schreibens der FIFA vom 12. August 2008 unzulässig sei und wies alle weiteren Rechtsbegehren ab. Das TAS erwog unter Hinweis auf R47 des TAS Code de l'arbitrage en matière de sport sowie Artikel 63.1 der Statuten der FIFA, dass ein Appeal nur gegen einen Entscheid zulässig sei. Das Schreiben der FIFA vom 12. August 2008 berühre die Rechtsstellung der Parteien jedoch nicht, sondern habe lediglich informativen Charakter und greife allfälligen Entscheidungen der zuständigen Organe der FIFA in dieser Angelegenheit nicht vor, weshalb es sich dabei nicht um eine Entscheidung handle, die beim TAS angefochten werden könne. C. Mit Beschwerde in Zivilsachen beantragt der Beschwerdeführer dem Bundesgericht, es sei der Entscheid des TAS vom 16. Dezember 2008 aufzuheben und die Sache an das TAS, eventualiter an das Players' Status Committee der FIFA, zurückzuweisen. Sowohl der Beschwerdegegner als auch die Vorinstanz schliessen auf Abweisung der Beschwerde.