Faits: A. Dans la nuit du 20 au 21 octobre 2005, aux environs de 1 heure, A._ était en compagnie de B._ et d'autres jeunes sur la terrasse d'un centre commercial. Ils ont empilé plusieurs tables en plastique pour en faire une muraille. Ils ont pris la fuite à l'arrivée d'un véhicule de police. Au même moment, X._, agent de la police de sécurité internationale en congé, promenait son chien dans les environs. Voyant l'arrivée d'une voiture de police et des jeunes qui partaient en courant, il a pensé qu'une infraction venait d'être commise et a décidé d'interpeller A._ qui avait pris sa direction. Il l'a sommé de s'arrêter. Comme le jeune homme n'obtempérait pas, X._ l'a ceinturé et fait tomber au sol, effectuant une clé de bras afin de l'immobiliser et le frappant à la tête. B. Par jugement du 18 février 2008, le Tribunal de police genevois a acquitté X._ de lésions corporelles simples. En bref, il a privilégié la version des faits du policier à celle de A._ et de B._. Il a en effet jugé que ce dernier n'était pas crédible en affirmant que le policier se trouvait debout tout en faisant une clé de bras, une telle position étant impossible au vu de sa dangerosité. C. Par arrêt du 24 novembre 2008 et statuant sur recours de A._, la Chambre pénale de la Cour de justice du canton de Genève a annulé la décision précitée et condamné X._, pour lésions corporelles simples, à une peine de 10 jours-amende à 50 fr/j, assortie d'un sursis de deux ans. Elle a considéré que le témoignage de B._ était probant et que le policier avait bien asséné des coups de pieds au plaignant, alors que celui-ci était au sol. D. X._ dépose un recours en matière pénale au Tribunal fédéral. Invoquant l'arbitraire, une violation du principe de la présomption d'innocence et de l'art. 14 CP, il conclut, principalement, à son acquittement. La Cour de justice n'a pas formulé d'observations. Le Procureur général et A._ ont conclu au rejet du recours. 