Faits: A. A.a Dès le début des années 80, les époux A._ et Dame A._ ont constitué ou fait constituer diverses sociétés afin de gérer les droits du personnage B._, créé par l'époux. Pour optimiser leur situation fiscale, ils sont entrés en relation d'affaires avec les époux X._ et Dame X._, ainsi qu'avec C._ SA, société fondée en 1987, sise à G._, puis à Meyrin, actuellement en liquidation suite à sa dissolution en 2011, propriété des époux X._, dont Dame X._ était administratrice présidente et X._, administrateur, avec signature collective à deux. Au fil des années, les époux A._ ainsi que D._ Ltd, dont ils étaient ayants droit économiques, ont confié aux époux X._ la gestion et l'administration d'une partie importante de leur patrimoine. Le 8 juin 1999, A._ a désigné ceux-ci en qualité d'exécuteur testamentaire pour l'exercice du droit moral sur l'ensemble de son ?uvre, conjointement avec, notamment, Dame A._. A la suite du décès de A._, en 2001, des différends sont apparus entre Dame A._ et D._ Ltd, d'une part, et les époux X._ et C._ SA, d'autre part. A.b De 2002 à 2010, Y._, avocat à G._, a agi en qualité de conseil de la société C._ SA. Il a exécuté son mandat en lien avec le litige précité. A.c Le 4 février 2011, Y._ a adressé à Dame X._ et X._ une note d'honoraires pour les prestations fournies dans les dossiers "succession A._, B.A._ SA, B.B._ SA et B.C._ SA" pour la période du 28 mars 2006 au 31 décembre 2010, d'un montant de 338'715 fr. (pour 752.7 heures de travail), auquel s'ajoutaient les montants de 150'000 fr. d'honoraires de résultat, 4'064 fr. de frais et 37'451 fr. 20 de TVA, pour une somme totale de 530'230 fr. 20. B. B.a Le 3 juin 2011, Y._ a requis du Juge de paix du district de Nyon le séquestre, à concurrence d'un montant de 530'230 fr. 20, plus intérêt à 5% l'an dès le 1er février 2011, d'un immeuble dont les époux X._ sont propriétaires à E._ ainsi que de l'ensemble des meubles le garnissant. En substance, il a allégué avoir déployé de manière ininterrompue, entre les mois de mars 2002 et décembre 2010, une activité de conseil et judiciaire dans divers domaines du droit suisse et international. Au sujet du résultat du mandat, il a allégué que le litige opposant ses clients à la succession A._ avait abouti, au mois de novembre 2009, à la signature et à l'exécution d'une transaction extra-judiciaire globale liquidant les rapports contractuels et patrimoniaux entre les parties, par laquelle ses clients avaient obtenu, en substance, une rémunération nette et d'autres avantages - notamment la renonciation par la succession à leur réclamer divers remboursements - de l'ordre de 15'000'000 fr. Par ordonnance du 6 juin 2011, le Juge de paix du district de Nyon a ordonné contre Dame X._ et X._, pour la créance invoquée fondée sur la note d'honoraires du 4 février 2011, le séquestre de l'immeuble précité et des meubles le garnissant, le cas de séquestre étant celui de l'art. 271 al. 1 ch. 4 LP, et astreint le créancier à verser la somme de 53'000 fr. à titre de sûretés. B.b Les époux X._ ont formé une opposition au séquestre, en soutenant notamment que le séquestrant avait été l'avocat de C._ SA, eux-mêmes étant représentés en Suisse par un autre conseil, et que, au demeurant, aucun honoraire de résultat n'avait été convenu. Par prononcé du 16 novembre 2011, le Juge de paix du district de Nyon a rejeté l'opposition. En substance, il a retenu que le séquestrant était fondé à facturer ses honoraires aux opposants, ceux-ci gérant la société C._ SA conjointement avec leurs affaires privées, que le tarif horaire facturé était parfaitement usuel, que l'honoraire de résultat facturé était justifié, le séquestrant ayant rendu vraisemblable qu'il avait favorisé les opposants d'un gain de 15'000'000 fr. environ, que le lien de la créance avec la Suisse était évident et que, domiciliés en Belgique depuis le 10 novembre 2010, les opposants étaient propriétaires d'un immeuble en Suisse. B.c Par acte du 5 mars 2012, Dame X._ et X._ ont formé un recours contre ce prononcé, concluant à sa réforme en ce sens que l'opposition au séquestre est admise, l'ordonnance de séquestre annulée et le séquestre levé. Par arrêt du 13 juillet 2012, la Cour des poursuites et faillites du Tribunal cantonal vaudois a rejeté le recours et déclaré l'arrêt exécutoire. C. Par acte posté le 15 août 2008, Dame X._ et X._ exercent un recours en matière civile contre cet arrêt. Ils concluent à sa réforme, en ce sens que leur opposition au séquestre n°x'xxx'xxx est admise, l'ordonnance de séquestre du Juge de paix du district de Nyon est annulée et le séquestre est levé. Ils invoquent l'arbitraire, au sens de l'art. 9 Cst., dans l'établissement des faits, en tant que l'autorité cantonale a admis la vraisemblance de l'importante intrication de leurs intérêts et de ceux de C._ SA et des honoraires réclamés, ainsi que dans l'application du droit, en tant que l'autorité cantonale a retenu qu'il y avait une société simple entre eux et C._ SA et que l'intimé était en droit de fixer ses honoraires en fonction du résultat que l'exécution de son mandat avait permis d'obtenir en leur faveur. Des observations n'ont pas été requises.