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. 