Faits: A. Par jugement du 10 septembre 2011, le Tribunal d'application des peines et mesures genevois (ci-après: TAPEM) a prononcé à l'encontre de X._ une peine privative de liberté de 21 jours en substitution de 42 amendes d'un montant total de 2140 francs. B. Par arrêt du 13 mars 2012, la Chambre pénale d'appel et de révision de la Cour de justice genevoise a déclaré la requête en révision du jugement du TAPEM du 10 septembre 2011 déposée par X._ irrecevable. En bref, il ressort les éléments suivants de cet arrêt. Le Service des contraventions de Genève a prononcé à l'encontre de X._ 42 amendes pour infractions à l'art. 48 OSR (violation des règles en matière de stationnement) commises entre le 29 avril et le 23 octobre 2010. Les décisions y relatives ont été adressées à X._, à son domicilie en France. Il n'a ni payé, ni contesté ces amendes. Le 24 juin 2011, le Service des contraventions a requis du TAPEM, la conversion des amendes en peine privative de liberté. Le 6 juillet 2011, le TAPEM a adressé, par pli recommandé, une convocation au recourant à l'audience fixée au 7 septembre 2011, qui lui a été retournée avec la mention « refusé ». Le recourant ne s'est pas présenté à l'audience précitée. Le 10 septembre 2011, le TAPEM a notifié à X._ son jugement par lequel il a converti les 42 amendes d'un montant total de 2140 fr. en 21 jours de peine privative de liberté. Le recourant a formé appel contre ce jugement le 21 décembre 2011, appel jugé irrecevable car tardif. Le 2 mars 2012, le recourant a déposé une demande de révision auprès de la Chambre pénale d'appel et de révision de la Cour de justice genevoise, concluant à ce qu'il soit acquitté des amendes et à ce qu'il n'ait pas à exécuter la peine de substitution prononcée par le TAPEM. C. X._ forme un recours en matière pénale contre cet arrêt. Il conclut, sous suite de frais et dépens, principalement à la réforme de l'arrêt entrepris en ce sens qu'il est acquitté du paiement des 42 amendes et qu'il ne doit pas exécuter la peine de substitution de 21 jours et, subsidiairement, à l'annulation de la décision et au renvoi de la cause à l'autorité inférieure pour nouvelle décision. Invités à déposer des observations sur le recours, la cour cantonale y a renoncé en se référant aux considérants de son arrêt, alors que le Service des contraventions du canton de Genève a conclu à son rejet. X._ a renoncé à se déterminer sur ces écritures.