Fatti:
A. Nell'ambito di un procedimento penale aperto in Italia, la Procura della Repubblica presso il Tribunale di Brindisi ha chiesto il rinvio a giudizio, tra gli altri, di B._, A._ e C._, per il reato di concorso in corruzione per un atto contrario ai doveri d'ufficio (art. 110 e 319 del Codice penale italiano). Secondo l'autorità italiana, B._, consulente della D._S.p.A., e A._, imprenditore portuale e socio di B._, avrebbero concluso un accordo corruttivo con C._, allora sindaco di X._, per garantirsi un'importante commessa di carbone. Dalla prima metà del 2002, D._S.p.A. era infatti proprietaria della centrale termoelettrica di X._, alimentata a carbone, mentre B._ era agente per l'Italia della società E._Ltd a Singapore, che acquistava, per conto della D._S.p.A., dalle miniere indonesiane una qualità di carbone a basso contenuto di zolfo (denominato "Adaro"). La centrale termoelettrica in esercizio dal 1964 sarebbe stata destinata alla chiusura per la carenza di dispositivi di protezione ambientale, ma C._, dietro compenso, si sarebbe adoperato per mantenerla in esercizio in virtù del suddetto accordo corruttivo, garantendo la sottoscrizione della convenzione che prevedeva l'utilizzazione da parte di D._S.p.A. del carbone "Adaro" per la parziale alimentazione della centrale.
B. Con sentenza del 17 febbraio 2006 del Giudice per le indagini preliminari presso il Tribunale di Brindisi, emanata secondo il rito del patteggiamento, B._ è stato condannato a una pena di un anno e cinque mesi di reclusione. L'accusato ha inoltre versato un importo di EUR 330'000.--, di cui il giudice ha disposto la confisca.
Con sentenza del 30 gennaio 2009 della seconda sezione penale del Tribunale di X._, A._ è stato condannato, anche per altri fatti che qui non interessano, alla pena di cinque anni di reclusione. Contro questo giudizio, sia l'accusato sia il Pubblico ministero hanno interposto appello.
C. Con sentenza del 3 dicembre 2009, la Corte penale del Tribunale penale federale (TPF) ha riconosciuto B._ colpevole di ripetuto riciclaggio di denaro, per avere operato o fatto operare tra il 12 marzo 2003 e il 20 ottobre 2003 trasferimenti di denaro dalla relazione bancaria yyy a favore della relazione bancaria zzz, entrambe presso la F._ di Lugano, per un valore complessivo di USD 265'576.05. L'imputato è stato condannato a una pena detentiva di un mese, sospesa condizionalmente per un periodo di prova di due anni, a valere quale pena complementare a quella di un anno e cinque mesi di reclusione inflitta mediante la sentenza 17 febbraio 2006 del giudice italiano.
Nello stesso giudizio, A._ è stato riconosciuto autore colpevole del medesimo reato e di un ulteriore atto di riciclaggio di denaro, in relazione alla sostituzione del beneficiario del trust intestatario della citata relazione zzz, per un valore complessivo di USD 83'173.30. L'imputato è stato condannato alla pena di 210 aliquote giornaliere di fr. 410.-- ciascuna, per un totale di fr. 86'100.--, sospesa condizionalmente per un periodo di prova di due anni.
D. Con sentenza del 31 gennaio 2011, il Tribunale federale ha accolto un ricorso in materia penale di B._ contro il giudizio del TPF, annullandolo nella misura in cui concerneva la sua condanna e rinviando la causa al TPF per una nuova decisione (sentenza 6B_222/2010). Questa Corte ha in particolare ravvisato una violazione del principio accusatorio rilevando che, senza prospettare la modifica dell'accusa all'imputato, il TPF ha ravvisato il reato di riciclaggio esclusivamente nel trasferimento del prezzo della corruzione destinato al sindaco, mentre l'atto di accusa gli rimproverava di avere riciclato l'utile complessivo derivante dal commercio di carbone favorito dall'accordo corruttivo.
E. Statuendo sulla base di un nuovo atto di accusa del 2 settembre 2011, senza indire un dibattimento, con sentenza del 12 luglio 2012 la Corte penale del TPF ha riconosciuto B._ colpevole di ripetuto riciclaggio di denaro, per avere operato o fatto operare tra il 12 marzo 2003 e il 20 ottobre 2003 trasferimenti di denaro dalla relazione bancaria yyy a favore della relazione bancaria zzz, entrambe presso la F._ di Lugano, per un valore complessivo di USD 265'576.05. L'imputato è stato condannato a una pena detentiva di venti giorni, sospesa condizionalmente per un periodo di prova di due anni, a valere quale pena complementare alla pena di un anno e cinque mesi di reclusione inflitta mediante la sentenza 17 febbraio 2006 del giudice italiano.
F. B._ impugna questa sentenza con un ricorso in materia penale al Tribunale federale, chiedendo di annullarla e di essere prosciolto dall'accusa di riciclaggio di denaro. Postula inoltre il riconoscimento di un'indennità di fr. 86'208.50 per il rimborso delle spese legali causate dal procedimento penale. Il ricorrente fa valere l'accertamento arbitrario dei fatti e la violazione degli art. 97 e 305bis CP.
G. La Corte penale del TPF comunica di non presentare osservazioni e di rimettersi al giudizio del Tribunale federale. Il MPC chiede di respingere il gravame nella misura della sua ammissibilità.

Diritto:
1. Presentato dall'accusato, che ha partecipato alla procedura dinanzi alla precedente istanza, le cui conclusioni sono state disattese (art. 81 cpv. 1 lett. a e b n. 1 LTF), e diretto contro una decisione finale (<ref-law>) resa in materia penale (<ref-law>) dalla Corte penale del TPF (<ref-law>), il ricorso in materia penale, tempestivo (<ref-law>), è di massima ammissibile.
2. 2.1 La precedente istanza ha statuito sulla fattispecie senza svolgere un nuovo dibattimento. Ha rilevato che la legge non contiene disposizioni sul modo di procedere nel caso in cui, come in concreto, una causa le venga rinviata dal Tribunale federale per un nuovo giudizio. Ha ritenuto che la violazione del diritto di essere sentito constatata dal Tribunale federale doveva considerarsi sanata con l'emanazione del nuovo atto di accusa da parte del MPC e con la possibilità per l'imputato di proporre ulteriori atti istruttori. La Corte penale del TPF ha ritenuto che non v'era necessità di assumere altre prove e che dopo la prima sentenza non erano emersi elementi rilevanti per la fissazione della pena: con l'accordo delle parti, si poteva quindi prescindere dall'indire un nuovo dibattimento permettendo loro di formulare conclusioni scritte.
2.2 Nella citata sentenza 6B_222/2010 del 31 gennaio 2011 questa Corte ha annullato la condanna del ricorrente ravvisando una violazione del principio accusatorio da parte del TPF, ciò che implicava di massima il rifacimento del processo. Ha sostanzialmente rilevato che l'imputato era stato condannato per una fattispecie diversa da quella contemplata nell'atto di accusa, non prospettatagli al processo e pertanto non specificatamente oggetto del dibattimento. In seguito, il 2 settembre 2011, il MPC ha emanato un nuovo atto di accusa, determinando quindi nuovamente il tema del giudizio che la Corte penale del TPF era chiamata a pronunciare. Essa disponeva al riguardo di un potere d'apprezzamento completo, dovendo esaminare questioni sia di fatto sia di diritto per determinarsi sulla colpevolezza o meno dell'imputato. Si imponeva quindi in tali circostanze lo svolgimento di un dibattimento pubblico, che costituisce un principio fondamentale, importante non soltanto per la persona interessata, ma anche quale condizione per la fiducia nel funzionamento della giustizia (<ref-ruling> consid. 4a; <ref-ruling> consid. 5d).
I casi in cui si potrebbe ritenere superfluo un dibattimento sono infatti diversi da quello in esame e concernono in particolare fattispecie in cui il nuovo giudizio è circoscritto a questioni secondarie o limitato a una nuova commisurazione della pena dopo che il Tribunale federale ha già statuito definitivamente sulla colpevolezza dell'imputato (cfr. sentenze 6B_864/2010 del 25 gennaio 2011 consid. 2, in: ius.focus 3/2011, n. 80 e 6P.104/2000 del 1° settembre 2000 consid. 3). Visto l'esito del ricorso non occorre comunque approfondire oltre la questione esaminando in particolare se, dando il loro consenso alla soluzione adottata dal TPF, le parti hanno comunque rinunciato validamente al dibattimento.
3. 3.1 Il ricorrente fa valere la violazione dell'<ref-law>. Sostiene che, poiché gli atti di riciclaggio addebitatigli sarebbero stati commessi tra il 12 marzo 2003 e il 20 ottobre 2003, l'azione penale era prescritta prima che fosse emanata la sentenza di condanna del 12 luglio 2012. A suo dire, il giudizio di condanna del 3 dicembre 2009, annullato da questa Corte, non sarebbe stato idoneo ad estinguere la prescrizione, siccome era basato su una fattispecie non contemplata nell'atto di accusa. Determinante sarebbe infatti l'atto di accusa del 2 settembre 2011, che sottoporrebbe per la prima volta al giudizio del TPF i fatti incriminati.
3.2 L'azione penale per il perseguimento del reato di riciclaggio si prescrive in sette anni (art. 305bis n. 1 in relazione con l'art. 97 cpv. 1 lett. c CP). Giusta l'<ref-law>, se prima della scadenza del termine di prescrizione è stata pronunciata una sentenza di prima istanza, la prescrizione si estingue (cfr. sentenza 6B_771/2011 dell'11 dicembre 2012 consid. 1, destinata a pubblicazione). Ciò indipendentemente dall'inoltro di successivi rimedi giuridici e dal fatto che tale sentenza sia annullata in seguito all'accoglimento di un rimedio giuridico (cfr. sentenza 6B_983/2010 del 19 aprile 2011 consid. 4.2.3).
3.3 Come rettamente rilevato dalla precedente istanza, la sentenza del 3 dicembre 2009 estingue la prescrizione dell'azione penale giusta l'<ref-law>. Il fatto che tale sentenza sia stata successivamente annullata dal Tribunale federale nella misura in cui concerneva la condanna del ricorrente non ha influsso sull'intervenuta estinzione della prescrizione. Sotto questo profilo, il motivo dell'accoglimento del gravame non è rilevante. Né è determinante il fatto che, in seguito all'accertata violazione del principio accusatorio, il MPC ha emanato un nuovo atto di accusa, su cui si basa la sentenza qui impugnata. Tale atto di accusa concerne infatti lo stesso procedimento penale per riciclaggio di denaro ed il medesimo complesso di fatti perseguiti.
4. 4.1 Il ricorrente rimprovera alla Corte penale del TPF di avere accertato in modo arbitrario che il prezzo della corruzione del sindaco C._, oggetto del riciclaggio, ammonterebbe a un terzo degli importi confluiti in Svizzera sul conto yyy. Sostiene che tale accertamento non corrisponderebbe a quanto stabilito nelle sentenze italiane, che riporterebbero genericamente la promessa di pagare al sindaco un importo di 30-50 centesimi di dollaro per tonnellata di carbone venduta alla D._S.p.A. e di cedergli il 25 % delle quote della società G._S.p.A.. Rileva inoltre che nei procedimenti italiani è menzionato un versamento al sindaco di 2 miliardi di vecchie lire, in realtà non avvenuto, circostanza su cui la precedente istanza non si sarebbe espressa. Secondo il ricorrente, il criticato accertamento sarebbe manifestamente insostenibile anche perché si fonderebbe unicamente sulle dichiarazioni di A._, ritenendole credibili, senza tuttavia considerare la sua successiva ritrattazione, secondo cui la promessa di un terzo riguardava in realtà le quote della G._S.p.A. Adduce inoltre che le versioni rese da C._ e da A._ nei vari interrogatori presenterebbero divergenze riguardo alla natura degli indebiti vantaggi promessi. Ritiene altresì incongruente ammettere una suddivisione in ragione di un terzo ciascuno tra i tre protagonisti dell'utile derivante dal commercio del carbone, quando tale utile, accreditato sul conto yyy, veniva in realtà suddiviso a metà tra il ricorrente e A._, spettando poi esclusivamente a quest'ultimo (sulla quota di 1⁄2) l'onere di versare la parte destinata al sindaco.
4.2 La Corte penale del TPF ha accertato che un terzo dei soldi confluiti in Svizzera erano di spettanza del sindaco C._, ritenendo che ciò risultava dalle dichiarazioni di A._, la cui versione compariva più volte e risultava maggiormente credibile. Al riguardo ha essenzialmente richiamato le dichiarazioni di A._ riportate nella sentenza del 30 gennaio 2009 del Tribunale di Brindisi e quelle rilasciate nell'interrogatorio dell'8 novembre 2005.
Invero, al di là dell'accennato stralcio delle deposizioni di A._, la criticata quota di un terzo non appare accertata in modo sicuro e univoco nel giudizio italiano. L'imputazione relativa alla fattispecie di corruzione indicava infatti in generale l'accettazione da parte del sindaco di retribuzioni non dovute, che sarebbero consistite in una promessa di versargli 30-50 centesimi di dollaro a tonnellata di carbone, di partecipare alla G._S.p.A., nonché di avere ricevuto un importo di 2 miliardi di vecchie lire. Nel richiamato verbale di interrogatorio dell'8 novembre 2005 la questione relativa alla quota di un terzo è stata posta essenzialmente dal magistrato interrogante, ma le dichiarazioni di A._ appaiono generiche riguardo alla natura e all'entità dei vantaggi promessi al sindaco. D'altra parte, la precedente istanza ha ritenuto unicamente le due citate deposizioni di A._, ma non si è confrontata con le ulteriori versioni degli interessati, in particolare con le dichiarazioni del sindaco, esaminando se e in che misura confortavano quelle di A._. Né ha valutato queste dichiarazioni alla luce delle modalità di gestione e delle concrete operazioni eseguite sui conti yyy e zzz. Dinanzi al TPF il ricorrente aveva infatti evidenziato differenti versioni di A._ ed C._ ed aveva sollevato una serie di obiezioni apparentemente non prive di pertinenza, sulle quali i precedenti giudici non si sono però addentrati, limitandosi ad addurre genericamente che un'evoluzione per quanto riguarda le versioni dei fatti fornite dalle persone implicate può rientrare nella tattica difensiva in funzione degli elementi raccolti dalle autorità inquirenti nel corso dell'inchiesta. In sostanza, il criticato accertamento secondo cui un terzo degli averi confluiti sul conto yyy corrisponderebbe al compenso del sindaco, non è fondato su una valutazione complessiva degli elementi disponibili, spiegante i motivi per cui reggerebbe al di là di ogni ragionevole dubbio. D'altra parte, il TPF nemmeno ha sufficientemente illustrato i motivi secondo cui il ricorrente sapeva o quantomeno aveva preso in considerazione che un terzo dei valori in conto costituivano prezzo della corruzione. In queste circostanze, la censura relativa all'accertamento arbitrario dei fatti deve essere accolta.
5. Il ricorrente sostiene che, anche volendo ammettere che la parte destinata al sindaco sarebbe stata pagata facendo capo ai fondi sulla relazione bancaria zzz provenienti dal conto yyy, l'importo di USD 265'576.05 sarebbe stato accertato arbitrariamente dal TPF, poiché comprenderebbe anche versamenti non riconducibili alla fornitura di carbone all'impianto di X._. Lamenta inoltre una violazione dell'<ref-law>.
Ritenuto che, come visto, il prezzo della corruzione è stato accertato in modo arbitrario dalla precedente istanza e che il giudizio impugnato deve essere annullato già per questo motivo, queste censure non devono essere esaminate in questa sede.
6. Ne segue che il ricorso deve essere accolto. La sentenza impugnata è quindi annullata e la causa è rinviata alla precedente autorità per una nuova decisione. Non si prelevano spese giudiziarie (<ref-law>) e la Confederazione verserà al ricorrente un'indennità a titolo di ripetibili (<ref-law>). Non spetta per contro a questa Corte pronunciarsi in questa sede sulla rifusione delle spese sostenute dal ricorrente nella procedura dinanzi alle precedenti istanze.

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è accolto. La decisione impugnata è annullata e la causa è rinviata al Tribunale penale federale per una nuova decisione.
2. Non si prelevano spese giudiziarie.
3. La Confederazione (Ministero pubblico) verserà al ricorrente un'indennità di fr. 3'000.-- a titolo di ripetibili di questa sede.
4. Comunicazione al patrocinatore del ricorrente, al Ministero pubblico della Confederazione e alla Corte penale del Tribunale penale federale.