Faits: A. Par arrêt du 18 septembre 2008 et complément du 18 mai 2009, la Cour des affaires pénales du Tribunal pénal fédéral a notamment condamné M._, pour blanchiment d'argent, à une peine pécuniaire de 360 jours-amende au montant de 165 fr. par jour, dont 36 ferme et 324 avec sursis, le délai d'épreuve étant fixé à trois ans. Elle l'a également condamné à participer au paiement des frais de la cause à hauteur de 59'073 fr. Cette condamnation repose, en résumé et pour l'essentiel, sur les éléments suivants. A.a En 1999, le gouvernement de l'Etat de Rio de Janeiro a constitué une nouvelle entité de contrôle fiscal des grandes sociétés implantées dans l'Etat, soit l'Inspectorat des grands contribuables, qui était dirigé par A._ et chargé du redressement fiscal desdites entreprises, comprenant tant l'encaissement des impôts soustraits que les amendes y relatives. Cette structure rapportait plus de 80 % de la recette fiscale de l'Etat précité. Les agents de cette structure ont rapidement mis en place un système pour obtenir des sociétés inspectées qu'elles versassent des pots-de-vin en échange d'arrangements sur les amendes et redressements à encaisser par l'administration. En bref, ils désignaient un inspecteur qui se rendait dans les locaux de l'entreprise et lui demandait de produire divers documents à bref délai, sous peine d'amende. La brièveté du délai imparti avait pour but et conséquence de mettre l'entreprise dans l'impossibilité de l'observer, ce qui entraînait une série d'amendes et, avec la mise sous pression de la société, créait les conditions utiles au chantage. Apparaissait alors un intermédiaire étranger à l'administration fiscale, venant proposer à la société un accord de clôture d'inspection et/ou de remise finale d'amende contre paiement d'un pot-de-vin. Par l'acceptation de cet accord, l'entreprise voyait l'inspection clôturée, ce qui lui permettait, d'une part, d'éviter de payer de nouvelles amendes et, d'autre part, d'échapper à un redressement fiscal plus important. Par arrêt du 19 septembre 2007, le Tribunal régional fédéral de la 2ème région, statuant en appel, a confirmé la condamnation des trois agents fiscaux A._, B._ et C._, pour corruption passive notamment. A.b A._, B._ et C._ ont transféré, par le biais des services d'un changeur, l'argent issu du système de corruption exposé ci-dessus sur des comptes ouverts auprès de la banque D._, dont le siège était à Genève et qui disposait de succursales à Zurich et Lugano. Cette banque a été dissoute sans liquidation le 26 juin 2002, la banque E._ en ayant repris l'actif et le passif. Elle comprenait un Conseil d'administration et son Comité du Conseil, un Comité de Direction générale, un Comité de Direction locale pour chacune des succursales, un Comité de conformité, un organe de révision interne, des services juridiques et de compliance auprès du siège comme des succursales, ainsi que des chefs de groupe, des gestionnaires et des assistants gestionnaires. La banque D._ agissait également par ses Bureaux de représentation à l'étranger, fonctionnant notamment comme pourvoyeurs d'affaires. A.c M._ était chef du service "compliance" et, en cette qualité, membre du Comité de conformité. Il était notamment chargé de convoquer et d'établir l'ordre du jour des séances de ce Comité et, à ce titre, le principal responsable du suivi des points en suspens. Lors de la séance du Comité de conformité du 29 septembre 1998, une liste des comptes changeurs ouverts par la succursale de Zurich depuis 1992 a été soumise aux membres. Après discussion, il a été décidé de transmettre le dossier à la Direction générale pour décision au sujet de la politique en la matière sachant que l'existence de ces comptes était interdite par la CFB et pouvait poser des problèmes de blanchiment. Par courrier électronique du 30 mai 2000, G._ a attiré l'attention du Comité de Direction locale sur le fait que A._ était mentionné comme auditeur fiscal pour deux comptes et vendeur de machines agricoles pour un troisième. La question de la possibilité de l'exercice d'une activité accessoire pour un agent public PEP était ainsi posée. De même, l'existence de transferts internes exécutés en faveur d'autres fonctionnaires fiscaux et l'importance des avoirs en compte étaient également relevées. Le 26 juin 2000, G._ a envoyé une copie du courrier précité à N._, responsable de l'organe de révision interne, qui l'a ensuite transmis au Comité de conformité. Le 5 juillet 2000, G._ a transmis notamment à M._ le mémo de H._ et Q._ du 4 juillet 2000, par lequel ceux-ci confirmaient à F._ qu'ils connaissaient très bien, depuis de nombreuses années, A._, lequel avait une bonne situation familiale et vivait avec sa femme et ses enfants. Ils précisaient que le client travaillait toujours comme auditeur fiscal et, en sus (il était autorisé à exercer une seconde profession), comme vendeur à son compte, agissant en qualité d'intermédiaire entre des industries de machines agricoles et des acheteurs à l'extérieur du pays. Les fonds entrant sur ses comptes étaient les commissions qu'il percevait sur ces transactions. Lors de sa séance du 4 août 2000, le Comité de conformité a demandé à X._ d'enquêter sur la compatibilité des activités de A._ avec le maintien de ses comptes auprès de la banque D._. Le 4 septembre 2001, M._ a reçu une liste des PEP comprenant notamment les comptes de B._, C._ et A._, ce dernier figurant sous deux professions différentes. Lors de sa séance du 28 septembre 2001, le Comité de conformité est revenu sur la mission confiée à X._. Il s'est ainsi référé au courrier électronique de F._ du 10 juillet 2001, dans lequel celui-ci décrivait le profil de A._. Il a constaté que les informations recueillies ne permettaient pas de se prononcer valablement sur la provenance et l'arrière-plan économique des transactions de ces comptes et qu'une analyse plus approfondie devait être faite par la succursale de Zurich. Le suivi devait être assuré par G._ et M._, aucun délai n'étant fixé pour ce faire. Le patrimoine du client déposé sur ses deux comptes atteignait 12'200'000 USD et 1'100'000 USD. Par courrier du 26 novembre 2001, L._ a adressé à M._ les rapports sur les comptes PEP établis par les gestionnaires. Elle précisait qu'à son avis, la plupart des rapports sur les comptes qui avaient enregistré des transactions durant la période du 1er janvier au 31 octobre 2001 étaient peu significatifs et qu'elle était disposée à demander aux gestionnaires des informations qui le seraient plus. Un tableau annexé récapitulait les opérations sur les différents comptes de PEP ainsi que le solde de ceux-ci. Le 10 juin 2002, G._ et L._ ont adressé un procès-verbal au Comité de conformité et à M._, avec copie à F._ et X._. Ils y rappelaient les éléments essentiels relatifs à deux comptes. Le premier de ceux-ci avait été ouvert en 1998. Son bénéficiaire économique, A._, était employé au service des impôts de la région de Rio de Janeiro et le total des entrées de fonds depuis l'ouverture jusqu'à ce jour était d'environ 17'000'000 USD contre 1'000'000 USD de sorties. Lors d'un voyage au Brésil au mois de juin de l'année précédente, F._ avait eu l'occasion de rencontrer ce client qui lui avait donné des explications sur les transactions enregistrées sur ce compte, informations sur la base desquelles il avait écrit un rapport. Cependant, les importantes entrées de fonds reçues depuis le début 2002 ne correspondaient pas à ce qui avait été discuté avec le client. Ainsi, le montant attendu des entrées devait s'élever à environ 50'000 USD par mois. Or, les contrôles avaient permis de constater que les montants reçus via leur changeur étaient bien plus importants (soit environ 440'000 USD par mois). En ce qui concernait le second compte, le bénéficiaire en était également un fonctionnaire travaillant pour les impôts et totalisait des entrées de fonds, depuis son ouverture en 1999, de 8'300'000 USD contre environ 20'000 USD de sorties. Le 18 juin 2002, G._ a soumis le courrier de F._ du 3 juin 2002 à Y._, J._ et M._. F._ y indiquait notamment que Q._ lui avait encore confirmé les activités de A._ telles que décrites dans le mémo du 10 juillet 2001, que le volume des entrées de cette année était effectivement supérieur au cadre initial de 50'000 USD, que l'explication en était que le client travaillait pour une des plus grandes banques d'investissement ainsi que pour le plus grand groupe de boissons brésilien et qu'il percevait des honoraires de conseil pour ces activités. Le 26 juin 2002, L._ a prié M._ de soumettre le cas de A._ au Comité compétent au sein de la banque E._, ce qu'il a fait le 2 juillet 2002. B. M._ a déposé un recours en matière pénale au Tribunal fédéral. Il a conclu à sa libération des fins de la poursuite pénale et à son acquittement de l'infraction de blanchiment d'argent, subsidiairement, au renvoi de la cause au Tribunal pénal fédéral et, plus subsidiairement, à ce qu'il soit dit que la République fédérative du Brésil n'a pas la qualité de partie civile dans cette procédure.