Fatti:
A. A.a L'8 giugno 2003 verso le ore 04.30 a una festa a Iragna B._ è uscito dal capannone e ha iniziato a parlare con un gruppo di giovani. La discussione è degenerata: dopo essere stato spintonato B._ è caduto a terra ed è stato colpito con diversi pugni che gli hanno causato la frattura della mascella e la lacerazione del timpano. Dopo il pestaggio, l'aggressore si è dileguato.
A.b A seguito di questi fatti, è stata aperta un'inchiesta terminata il 9 novembre 2005 con l'emanazione di un decreto di accusa che proponeva la condanna di C._ per titolo di lesioni semplici. Statuendo sull'opposizione del condannato a tale decreto, il 6 giugno 2006 il Giudice della Pretura penale ha prosciolto C._ dall'accusa di lesioni semplici per insufficienza di prove.
In aula sono stati sentiti come testi, tra gli altri, D._ e A._. Quest'ultimo avrebbe ribadito, secondo quanto riportato in sentenza, sia di non aver visto sia di non aver partecipato al pestaggio e di non ricordarsi di aver notato C._ alla festa.
Adita dalla pubblica accusa, il 29 aprile 2008 la Corte di cassazione e di revisione penale del Tribunale d'appello del Cantone Ticino (CCRP) ha annullato la decisione di assoluzione e rinviato gli atti a un nuovo giudice della Pretura penale per nuovo giudizio.
B. Il 27 luglio 2006 è stato aperto un procedimento a carico di A._ per titolo di falsa testimonianza. Con sentenza dell'8 agosto 2008 il Presidente della Corte delle assise correzionali di Bellinzona ha riconosciuto A._ autore colpevole di falsa testimonianza per avere, in data 6 giugno 2006, reso, in qualità di testimone e dopo aver prestato giuramento, una falsa deposizione sui fatti relativi al procedimento penale a carico di C._. A._ è stato condannato alla pena unica - pena aggiuntiva a quella di 40 aliquote giornaliere di fr. 80.-- cadauna inflittagli precedentemente per fatti posteriori a quelli in esame - di fr. 16'800.-- corrispondenti a 210 aliquote giornaliere di fr. 80.-- cadauna, pena non sospesa condizionalmente.
In sostanza, il giudice ha accertato che A._ ha mentito nel pretendere di non essersi trovato a pochi metri dal luogo della lite quando questa è cominciata. Egli ha quindi dedotto da questo accertamento che A._ non poteva non essersi accorto del pestaggio.
C. Con sentenza del 17 febbraio 2009, la CCRP ha accolto il ricorso per cassazione presentato da A._ e lo ha prosciolto dall'imputazione di falsa testimonianza.
Secondo la Corte cantonale, sebbene l'accertamento dei fatti fosse scevro di arbitrio, il primo giudice ha fatto delle deduzioni insostenibili ritenendo che A._ non poteva non aver assistito al pestaggio di B._ avvenuto durante la festa di Iragna rispettivamente non poteva non aver notato la presenza alla festa di C._.
D. Il Procuratore pubblico impugna il giudizio dell'ultima autorità cantonale con ricorso in materia penale al Tribunale federale. Lamentando essenzialmente arbitrio nell'accertamento dei fatti e nella valutazione delle prove, postula l'annullamento della contrastata sentenza nonché, in via principale, la conferma integrale della decisione del Presidente della Corte delle assise correzionali di Bellinzona o, in via subordinata, il rinvio dell'incarto alla CCRP per nuovo giudizio.
E. Trasmettendo l'incarto cantonale al Tribunale federale, la CCRP ha comunicato di rinunciare a presentare osservazioni al gravame. Invitato a esprimersi sull'impugnativa, A._ conclude chiedendo che il ricorso sia respinto e la sentenza cantonale confermata.

Diritto:
1. A mente del ricorrente, annullando la sentenza di primo grado censurandola di arbitrio, la stessa CCRP sarebbe incorsa in arbitrio.
1.1 Nell'ambito dell'accertamento dei fatti e della valutazione delle prove la CCRP dispone di un potere analogo a quello del Tribunale federale chiamato a statuire su un ricorso per violazione del divieto dell'arbitrio (v. art. 288 del codice di procedura penale del 19 dicembre 1994; CPP/TI; RL 3.3.3.1). Secondo costante giurisprudenza, adito con un ricorso fondato sull'<ref-law> e avente per oggetto la decisione di un'autorità di ultima istanza che pure fruiva di una cognizione ristretta, il Tribunale federale non si limita ad esaminare dal punto di vista dell'arbitrio se l'autorità di ricorso lo abbia commesso; in altri termini, non vi è la cosiddetta duplice limitazione del potere di esame (Willkür im Quadrat). Il Tribunale federale esamina liberamente la questione di sapere se l'autorità cantonale ha a torto ammesso - rispettivamente negato - una violazione del divieto dell'arbitrio (<ref-ruling> consid. 1a/cc; <ref-ruling> consid. 2b).
1.2 Nella contrastata sentenza, la CCRP ha ritenuto che la ricostruzione dei fatti avvenuti l'8 giugno 2003 da parte del primo giudice fosse scevra di arbitrio, reggendo anzi anche a un libero esame.
Sulla scorta delle dichiarazioni dei testi D._ (un'amica di B._) e E._ (un giovane pure presente alla festa e che aveva assistito alla lite), il primo giudice ha accertato che A._ si trovava a pochi metri dalla lite quando questa scoppiò.
A questo proposito l'opponente sostiene che le deposizioni dei precitati testi non collidono, entrambi avendo dichiarato che stavano parlando con lui nel momento in cui la discussione tra B._ e il suo aggressore è degenerata. Di conseguenza, uno di loro o entrambi mentono. L'apparente incongruenza tra le due deposizioni è stata però chiarita dalla CCRP. Su questo punto il Tribunale federale può quindi rimandare ai pertinenti considerandi della decisione dell'ultima istanza cantonale (<ref-law>; sentenza impugnata consid. 6 pag. 7 seg.).
L'opponente ritiene inoltre che le dichiarazioni dei testi D._ e E._ sono risultate confuse, imprecise e variate nel tempo su alcuni elementi determinanti, rinviando per i dettagli alle pagine del suo ricorso per cassazione cantonale. Orbene, dinanzi al Tribunale federale, le motivazioni devono essere contenute nell'atto di ricorso o nella risposta. Un rinvio agli atti cantonali non è sufficiente sotto il profilo dell'art. 42 cpv. 1 e 2 LTF. Non spetta infatti al Tribunale federale completare lo scritto sottoposto al suo esame andando a consultare le impugnative presentate in sede cantonale (v. <ref-ruling> consid. 3.2). Ne consegue che, nella misura in cui l'opponente rimanda alle argomentazioni sviluppate davanti alla CCRP, tali argomentazioni non possono essere prese in considerazione da questo Tribunale.
1.3 Dall'accertamento che A._ si trovasse a pochi metri dalla lite quando questa scoppiò, la CCRP ha tuttavia negato che si potesse dedurre che egli non potesse non essersi accorto di quanto successo, ossia del pestaggio. In concreto, per l'ultima autorità cantonale, numerosi elementi tratti dalle dichiarazioni agli atti, segnatamente quella di D._, depongono per il contrario. Secondo quanto affermato dalla ragazza, una volta messisi in disparte, lei e A._ si sono messi a parlare, tra loro e i contendenti vi erano diverse persone in piedi che ostacolavano la vista ed era buio. In seguito A._ si è allontanato tanto che la ragazza non lo ha più visto. Sicché, continua la CCRP, la conclusione del primo giudice per cui A._ non può non aver visto il pestaggio, in altri termini il momento in cui B._ è stato preso a pugni quando era già a terra, è arbitraria perché non suffragata da alcun elemento e in aperto contrasto con le risultanze istruttorie.
1.4 A mente del ricorrente, la conclusione del giudice di prima istanza poggia non solo sul principio dell'ordinario andamento delle cose e dell'esperienza generale di vita, ma anche sulle risultanze di cui al procedimento penale. E._ ha affermato che all'esterno del capannone vi era un gruppo di persone, quantificato da D._ in 10/15. Non si trattava quindi di una folla tale da impedire, se del caso, la visuale di quanto stava accadendo. Nonostante le condizioni del momento (buio, persone frapposte), sia E._ che D._, presenti sul luogo, hanno seguito la scena del pestaggio perché naturalmente attirati dalla stessa. Un pestaggio attira forzatamente l'attenzione dei presenti. E._ inoltre ha affermato di non aver discusso dell'episodio con C._ e A._ se non quando gli hanno detto che erano stati chiamati dalla Polizia a cui non avevano detto niente, nel senso che non avevano detto che a litigare e aggredirsi con B._ era stato C._. Per il ricorrente, l'unica spiegazione delle precitate affermazioni è che A._, non solo fosse presente al momento dei fatti, ma li abbia pure visti. Anche la teste D._ ha riferito di aver incontrato, qualche giorno dopo l'accaduto, A._ che le avrebbe domandato come stava il suo amico, ovvero B._. Secondo il ricorrente, A._ conosceva il fatto perché ne era stato testimone oculare.
2. 2.1 La valutazione della dichiarazione ritenuta falsa va fatta tenendo conto della situazione globale e dell'insieme delle circostanze del caso che, in concreto, comprendono anche l'intera vicenda processuale conseguente al pestaggio dell'8 giugno 2003. Questa vicenda ha conosciuto invero un iter travagliato. In una prima fase, infatti, la responsabilità dell'autore non poté essere accertata, il presunto autore negando qualsiasi implicazione e pretendendo di trovarsi altrove. In questa prima fase, le deposizioni di A._ di non aver visto il pestaggio e di non ricordare di aver visto C._ alla festa giocarono un ruolo certo nell'accertamento della responsabilità del presunto autore e indebolirono la prova a carico di C._ fornita da D._. Inoltre, la dichiarazione di A._ di non aver incontrato D._ se non all'interno del capannone si scontrò con il ricordo della ragazza di essersi intrattenuta con lui all'esterno di detto capannone e di essere stata con lui nel momento in cui cominciò il pestaggio.
Il successivo ritrovamento di un altro testimone, E._, ha mutato il corso delle indagini e modificato sensibilmente il grado di credibilità degli altri testi. E._ ha infatti dichiarato che C._ era l'autore del pestaggio, confermando così quanto in precedenza affermato da D._. Si trattava proprio di quel C._ che A._ non ricordava di aver visto alla festa. E._ ha inoltre asserito che la sera dell'8 giugno 2003 era in compagnia di C._ e di A._. Hanno iniziato la serata in un ritrovo di Olivone, hanno poi deciso di recarsi a Iragna dove sapevano esserci delle feste. A fine serata, dopo aver separato C._ dall'altro contendente, se ne sono subito andati: di sicuro lui, C._ e A._ (v. dichiarazioni di E._ riprodotte nella sentenza di primo grado pag. 11 e 12). E._ ha altresì affermato di aver assistito al pestaggio, scena a cui non aveva mai assistito e difficile da non ricordare.
2.2 La svolta intervenuta nell'indagine penale ha permesso di accertare che A._ mentì sulla circostanza di non essersi trovato all'esterno del capannone al momento del pestaggio, a pochi metri dal luogo in cui avveniva.
I testi D._ e E._ sono stati ritenuti attendibili dal Presidente della Corte delle assise correzionali. Questa valutazione non è stata criticata dalla CCRP.
2.3 Dalle dichiarazioni riportate nella sentenza di primo grado emerge che, nonostante il buio e la presenza di altra gente, sia E._ che D._ hanno percepito e visto il pestaggio. Come pertinentemente osservato dal ricorrente, si tratta di un evento che attira, per forza di cose, l'attenzione dei presenti, come del resto confermato da D._ per cui, quando la discussione tra B._ e l'altra persona è degenerata, l'attenzione di tutti si è focalizzata su quello che stava accadendo (v. sentenza di primo grado pag. 13). Il buio e le persone frapposte non sono quindi elementi che permettano di escludere che anche A._ abbia visto il pestaggio, tanto meno considerando che non vi è stato un unico pugno che possa essere sfuggito al suo sguardo, bensì una successione intera di pugni. Certo, non si conosce la posizione in cui si trovava l'opponente nel momento in cui B._ veniva preso a pugni. Nel censurare di arbitrarie le deduzioni tratte dal giudice di merito, la CCRP ha tuttavia omesso di valutare nel loro insieme le dichiarazioni dei testimoni, segnatamente l'atteggiamento dell'opponente dopo i fatti. E._ ricorda infatti di aver incontrato A._ e C._ qualche tempo dopo i fatti, i quali gli hanno riferito di non aver detto nulla alla Polizia. Da parte sua, anche D._ ha incontrato, dopo l'accaduto, A._ che le ha domandato come stesse B._, alludendo implicitamente alle conseguenze del pestaggio. Accertato che A._ era presente al momento dei fatti a distanza di pochi metri, l'unica spiegazione alle affermazioni appena esposte è che, come sostenuto dal ricorrente, li aveva visti.
2.4 Quanto poi alla dichiarazione di non aver visto C._ alla festa, questa è smentita da quanto affermato da E._ e, indirettamente da D._, dimostratisi testi attendibili. In particolare, il primo ha preteso che dopo essersi incontrati a Olivone si sono diretti a Iragna e a fine serata, una volta separati i contendenti, se ne sono andati, anche se non sulla medesima auto. L'opponente contesta che i tre siano giunti insieme alla festa non essendo né dimostrato né confermato da un altro testimone e sottolinea come E._ non fosse sicuro che a fine serata A._ fosse partito con lui e C._. Come già esposto, E._ si è rivelato essere un teste attendibile a cui anche la CCRP sembra aver dato credibilità. La questione di sapere se i tre abbiano lasciato insieme la festa non è in questa sede decisiva, va comunque precisato che l'esitazione di E._ sembra più concernere il viaggio in auto piuttosto che il fatto di lasciare insieme la festa (v. verbale di interrogatorio di E._ del 26 luglio 2006 pag. 2 unitamente al verbale di interrogatorio di E._ del 23 marzo 2007 pag. 1 nonché verbale del dibattimento dell'8 agosto 2008 pag. 3). E._ non ha però avuto dubbi sul fatto che i tre si siano recati di comune accordo alla festa a Iragna.
2.5 Come rilevato dal ricorrente, la CCRP non si è posta alcun interrogativo in merito ai motivi delle menzogne (comprovate) dell'opponente circa la sua presenza sul luogo e al momento dell'alterco e successivo pestaggio. Tenuto conto dei considerandi che precedono, la conclusione avanzata dal ricorrente e condivisa da questa Corte è che A._ ha mentito per non dover testimoniare contro l'amico C._ che ha visto mentre aggrediva B._.
In conclusione l'autorità cantonale ha, a torto, ammesso una violazione del divieto dell'arbitrio incorrendo così essa stessa nell'arbitrio. Il ricorso del Ministero pubblico va dunque accolto.
3. 3.1 Se accoglie il ricorso, il Tribunale federale giudica esso stesso nel merito o rinvia la causa all'autorità inferiore affinché pronunci una nuova decisione. Può anche rinviare la causa all'autorità che ha deciso in prima istanza (<ref-law>).
Nelle sue conclusioni il ricorrente ha postulato l'annullamento della sentenza della CCRP nonché, in via principale, la conferma integrale del giudizio reso in prima istanza e, in via subordinata, la trasmissione degli atti alla CCRP per nuovo giudizio.
Dalla decisione impugnata risulta che, nel suo ricorso alla CCRP, A._ ha concluso, in via principale, al suo proscioglimento da ogni addebito, in via subordinata, all'annullamento della sentenza della Corte delle assise correzionali e al rinvio degli atti al Tribunale penale cantonale per un nuovo giudizio e, in via ancor più subordinata, alla riduzione della pena inflittagli e alla sua sospensione condizionale. Poiché la CCRP ha (a torto, v. consid. 2) prosciolto l'opponente dall'imputazione di falsa testimonianza accogliendo le sue principali conclusioni, non si è pronunciata sulle conclusioni, formulate in via subordinata, relative alla pena. In simili circostanze, il Tribunale federale non può che rinviare l'incarto all'ultima autorità cantonale affinché decida della ricevibilità e fondatezza delle conclusioni subordinate formulate dinanzi a essa da A._.
3.2 Il ricorso si è rivelato fondato. Non si prelevano pertanto spese giudiziarie (v. <ref-law>).
Seppur invitato a esprimersi sul gravame, risultando soccombente in questa procedura, all'opponente non viene riconosciuta alcuna indennità per ripetibili (<ref-law>). Neppure al ricorrente, incaricato di compiti di diritto pubblico, non sono accordate spese ripetibili (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è accolto e la decisione emanata dalla Corte di cassazione e di revisione penale il 17 febbraio 2009 è annullata. La causa viene rinviata alla Corte di cassazione e di revisione penale per nuovo giudizio.
2. Non si prelevano spese giudiziarie.
3. Non si accordano ripetibili per la sede federale.
4. Comunicazione alle parti e alla Corte di cassazione e di revisione penale del Tribunale d'appello del Cantone Ticino.