Fatti: A. A.a A._ ha lavorato quale funzionario pubblico presso l'Ufficio U._ della Regione Autonoma Valle D'Aosta. A partire dall'ottobre 2000, a seguito dell'alluvione che ha colpito la Valle d'Aosta, approfittando della sua posizione di preposto alle procedure urgenti di assegnazione di lavori post-alluvione, A._ ha incassato varie somme di denaro da alcune imprese della regione in cambio dell'attribuzione degli appalti legati a opere di costruzione. Nel periodo compreso tra il 2000 e il 2003, avvalendosi talvolta anche dell'aiuto di D._ e E._, A._ ha versato gran parte delle tangenti ricevute su svariati conti bancari in Svizzera, e meglio su relazioni aperte presso la F._SA a X._, presso la V._ a X._, divenuta in seguito W._, e presso la banca I._SA a Y._, divenuta poi banca J._SA. Della gestione dei conti si sono occupati due consulenti bancari: B._, attivo presso la V._ a X._, e C._, attivo presso la F._SA a X._. A.b Il 18 novembre 2003 A._ è stato arrestato in Italia con l'accusa di corruzione. Riconoscendo sostanzialmente i fatti contestatigli dalle autorità penali italiane, con sentenza di patteggiamento del 4 aprile 2006, il Giudice per le indagini preliminari (GIP) ha condannato A._ alla pena di un anno, undici mesi e dieci giorni di reclusione, sospesa condizionalmente, e ha ordinato la confisca di euro 400'000.--, quale prezzo della corruzione. B. B.a Venute a conoscenza dell'arresto di A._ attraverso la stampa italiana, l'8 dicembre 2003 le banche I._SA e F._SA a Y._, sospettando un legame tra le accuse di corruzione e il denaro da loro gestito, hanno segnalato il caso all'Ufficio di comunicazione in materia di riciclaggio di denaro (MROS) che ha a sua volta trasmesso la comunicazione al Ministero pubblico della Confederazione (MPC). B.b È stato quindi aperto un procedimento penale nei confronti di A._ e ignoti per titolo di riciclaggio di denaro, poi esteso anche contro D._ e E._. Nel corso dell'indagine preliminare, il MPC ha ordinato la perquisizione e il sequestro di diversi conti bancari di pertinenza di A._, tra cui il conto d'attesa di cassa uuu presso la banca I._SA a Y._, poi divenuto conto vvv presso la banca J._SA a Y._, nonché i conti www e yyy presso F._SA a X._. In seguito, si è pure proceduto alla perquisizione e al sequestro del contenuto della cassetta di sicurezza zzz presa in affitto da A._ presso la F._SA di X._. Su richiesta del MPC, in data 28 febbraio 2005 l'Ufficio dei giudici istruttori federali (UGI) ha aperto un'istruzione preparatoria nei confronti di A._, D._, E._ e ignoti per il reato di riciclaggio di denaro. Sospettando che, mediante l'assistenza da loro prestata, i due consulenti bancari avessero partecipato all'attività di riciclaggio contestata a A._, l'istruzione è stata successivamente estesa anche a B._ e C._. Il 31 agosto 2006, il procedimento a carico di D._ e E._ è stato disgiunto in quanto le autorità italiane si erano dichiarate disposte a riprendere il procedimento penale nei loro confronti. L'istruzione preparatoria si è conclusa il 10 marzo 2008. B.c Con atto d'accusa del 6 novembre 2008, il MPC ha chiesto al Tribunale penale federale di riconoscere A._, B._ e C._ colpevoli di ripetuto riciclaggio di denaro e di confiscare gli averi sequestrati sul conto presso la banca J._SA per un importo complessivo di euro 550'960.36. C. Con sentenza del 20 e 27 luglio 2009, la Corte penale del Tribunale penale federale (TPF) ha riconosciuto A._ colpevole di riciclaggio di denaro per cinque dei dieci capi d'accusa formulati dal MPC. Lo ha quindi condannato a una pena detentiva di venti giorni a valere quale pena complementare alla pena di un anno, undici mesi e dieci giorni di reclusione inflitta mediante sentenza di applicazione della pena su richiesta delle parti pronunciata il 4 aprile 2006 dal GIP del Tribunale di Aosta e ha sospeso l'esecuzione della pena, fissando a due anni il periodo di prova. Ha inoltre ordinato la confisca dei valori sequestrati nel conto vvv intestato a A._ presso la banca J._SA di Y._ a concorrenza dell'importo di fr. 534'263.80, dissequestrando l'eccedente nonché i conti aaa e yyy intestati a A._ presso la banca F._SA di X._. B._ e C._ sono invece stati prosciolti da tutte le accuse. D. Contro la sentenza del TPF, il MPC interpone ricorso in materia penale al Tribunale federale. Postula, in via principale, un parziale annullamento del giudizio impugnato e la sua conseguente riforma. Per quanto concerne A._ chiede che sia riconosciuto colpevole di riciclaggio di denaro anche in relazione al capo d'accusa 1.3 dell'atto di accusa e che sia stabilito che la somma complessiva riciclata ammonta a euro 445'110.36. Chiede inoltre di condannare A._ a una pena detentiva di dodici mesi sospesa condizionalmente, con un periodo di prova di due anni, cumulata a una multa di fr. 40'000.--, a valere quale pena complementare alla pena inflittagli dal GIP del Tribunale di Aosta il 4 aprile 2006. Con riguardo a B._ e a C._, domanda che siano riconosciuti colpevoli di riciclaggio di denaro e condannati ognuno a una pena pecuniaria di 300 aliquote giornaliere di fr. 300.-- cadauna, sospesa condizionalmente per un periodo di prova di due anni, cumulata a una multa di fr. 15'000.--. Infine, postula la confisca dei valori patrimoniali sequestrati per un importo complessivo di euro 550'960.36. In via subordinata, chiede il parziale annullamento della sentenza impugnata e il rinvio della causa al TPF per nuovo giudizio. Invitato a esprimersi sul ricorso, il TPF dichiara di non avere particolari osservazioni da formulare. A._ postula l'integrale conferma della sentenza di primo grado. B._ chiede che il ricorso venga integralmente respinto, mentre C._ propone la reiezione del gravame nella misura in cui è ammissibile. Delle osservazioni degli opponenti si dirà, per quanto necessario, nei considerandi. E. Con decreto del 2 febbraio 2010 al ricorso è stato conferito un parziale effetto sospensivo: è stato mantenuto a concorrenza di euro 550'960.36 il sequestro degli averi nel conto vvv intestato a A._ presso la banca J._SA di Y._.