Sachverhalt: A. X._ und Y._, beide mit Wohnsitz in Buenos Aires/Argentinien, (Beschwerdeführer) sind als Spielervermittler tätig. Mit Vertrag vom 30. Juni 2003 wurden die beiden Beschwerdeführer vom Club B._, einem argentinischen Fussballverein beauftragt, den Transfer des Fussballspielers Z._ zum Fussballclub A._ (Beschwerdegegner) auszuhandeln und abzuwickeln. Der Vertrag sah vor, dass die Beschwerdeführer den Fussballverein B._ exklusiv bis zum 30. August 2003 vertreten durften. Im Gegenzug verpflichtete sich B._, den Beschwerdeführern 10 % der Transfersumme als Vergütung zu entrichten. Für den Fall der Nichterfüllung seitens B._ wurde der doppelte Betrag (d.h. 20 % der Transfersumme) als Konventionalstrafe vereinbart. Am 8. Juli 2003 schlossen B._, der Beschwerdegegner sowie eine Gesellschaft, die an den Transferrechten des Spielers beteiligt war, einen Vertrag über den Transfer von Z._ von B._ zum Beschwerdegegner gegen eine Transfersumme von EUR 3'500'000.-- ab (nachfolgend Transfervertrag). Der Transfervertrag wurde unter der aufschiebenden Bedingung abgeschlossen, dass Z._ nach erfolgreicher medizinischer Untersuchung einen Arbeitsvertrag mit dem Beschwerdegegner abschliesse. Anlässlich der medizinischen Untersuchung vom 21. Juli 2003 erachteten die Ärzte des Beschwerdegegners die körperliche Verfassung des Spielers für unzureichend. Entsprechend erklärte der Beschwerdegegner die aufschiebende Bedingung als nicht erfüllt und verzichtete auf die Unterzeichnung des Arbeitsvertrags mit dem Spieler. Einige Tage später kam es zu einem Transfer von Z._ zu einem anderen Fussballclub. B. In der Folge machten die Beschwerdeführer vor der Fédération Internationale de Football Association (FIFA) gestützt auf die FIFA-Bestimmungen sowie Art. 41 OR eine Schadenersatzforderung über EUR 700'000.-- gegen den Beschwerdegegner geltend. Der zuständige Einzelrichter wies die Klage ab. Diesen Entscheid bestätigte das Tribunal Arbitral du Sport (TAS) mit Schiedsurteil vom 29. Februar 2008 auf Appellation der Beschwerdeführer hin. C. Mit Beschwerde in Zivilsachen beantragen die Beschwerdeführer dem Bundesgericht, das Urteil des TAS vom 29. Februar 2008 sei aufzuheben. Zudem sei der Beschwerdegegner zu einer Entschädigung von EUR 700'000.-- plus Zins zu 5 % seit dem 8. Juli 2003 zu verurteilen. Schliesslich beantragen die Beschwerdeführer die Edition verschiedener Dokumente bzw. Aufzeichnungen. Der Beschwerdegegner sowie das TAS schliessen auf Abweisung der Beschwerde, soweit überhaupt darauf einzutreten sei. D. Mit Verfügung vom 24. Juni 2008 wurde das Sicherstellungsbegehren des Beschwerdegegners abgewiesen.