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'<ref-law> (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.

Considérant en droit:
1. Le recourant se plaint d'une violation des <ref-law> et 385 CP.
1.1 La demande de révision est postérieure à l'entrée en vigueur du CPP. Il s'ensuit que les règles de compétence et de procédure des <ref-law> s'appliquent. Les motifs de révision pertinents sont en revanche ceux prévus par le droit applicable au moment où la décision dont la révision est demandée a été rendue. Cette réserve est toutefois sans portée s'agissant d'une révision en faveur du condamné, le motif de révision prévu à l'<ref-law> correspondant à celui de l'<ref-law> (arrêt 6B_310/2011 du 20 juin 2011 consid. 1.1; 6B_41/2012 du 28 juin 2012 consid. 1.1 et les références citées).
1.2 La demande de révision peut notamment être dirigée contre un jugement entré en force ou une décision judiciaire ultérieure (<ref-law>).
Dans sa demande de révision, le recourant a en particulier conclu à son acquittement des 42 amendes. Autrement dit, il a requis la révision des amendes. De telles décisions peuvent être assimilées à des jugements au sens de l'<ref-law> (cf. <ref-ruling> consid. 2a p. 250; Message du 21 décembre 2005 relatif à l'unification du droit de la procédure pénale, FF 2006 1057, p. 1303 ad art. 417 [actuel <ref-law>]; MARIANNE HEER, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, no 21 ad <ref-law>). Elles peuvent par conséquent faire l'objet d'une demande de révision.
1.3 L'<ref-law> prévoit notamment que toute personne lésée par un jugement entré en force, une ordonnance pénale, une décision judiciaire ultérieure ou une décision rendue dans une procédure indépendante en matière de mesures peut en demander la révision s'il existe des faits ou des moyens de preuve qui étaient inconnus de l'autorité inférieure et qui sont de nature à motiver l'acquittement ou une condamnation sensiblement moins sévère du condamné.
Cette disposition reprend en particulier la double exigence posée par l'<ref-law> selon laquelle les faits ou moyens de preuve invoqués doivent être nouveaux et sérieux (arrêt 6B_455/2011 du 29 novembre 2011 consid. 1.2 et les références citées).
Les faits ou moyens de preuve sont nouveaux lorsque le juge n'en a pas eu connaissance au moment où il s'est prononcé, c'est-à-dire lorsqu'ils ne lui ont pas été soumis sous quelque forme que ce soit (<ref-ruling> consid. 1 p. 73).
Les faits et moyens de preuve sont sérieux lorsqu'ils sont propres à ébranler les constatations de fait sur lesquelles se fonde la condamnation et que l'état de fait ainsi modifié rend possible un jugement sensiblement plus favorable au condamné (<ref-ruling> consid. 1 p. 73).
1.4 Le recourant a fait valoir dans sa demande de révision, pièces à l'appui, qu'au moment des faits à l'origine des différentes amendes, il n'était plus le propriétaire du véhicule concerné, qu'il avait vendu. Il s'agit effectivement là d'un fait et de moyens de preuve qui peuvent être qualifiés de nouveaux et sérieux et qui sont susceptibles d'aboutir à une révision selon l'<ref-law>.
1.5 On comprend de la brève motivation de la cour cantonale qu'elle a refusé d'entrer en matière sur la demande de révision du recourant en raison d'un prétendu abus de droit de celui-ci. Elle s'est en particulier référée à l'arrêt publié aux <ref-ruling>.
1.6 La jurisprudence considère qu'une demande de révision dirigée contre une ordonnance pénale doit être qualifiée d'abusive si elle repose sur des faits que le condamné connaissait initialement, qu'il n'avait aucune raison légitime de taire et qu'il aurait pu révéler dans une procédure ordinaire mise en ?uvre par une simple opposition (<ref-ruling> consid. 2.3 p. 75).
1.7 En l'espèce, la cour d'appel n'a pas exposé en quoi la procédure suivie pour le prononcé des amendes, encore régie par le droit cantonal, correspondait au régime de l'ordonnance pénale. Quoi qu'il en soit, sur la base du dossier, il n'apparaît pas qu'un abus de droit puisse être opposé au recourant. En effet, celui-ci a allégué qu'il avait chargé son garagiste de régler cette affaire (cf. demande de révision p. 3 ch. 8). Ce garagiste avait lui-même adressé en août 2010 un formulaire au Service des contraventions indiquant que le dénommé A._ - qui avait acquis le véhicule du recourant - l'avait revendu à une tierce personne et que ce service était invité à tenir compte du véritable détenteur (cf. pièce 5; <ref-law>). Il apparaît ainsi que le Service des contraventions a omis de tenir compte de cette information et a continué à infliger des amendes au recourant pour un véhicule dont il ne disposait plus. Dans ce contexte particulier, on ne saurait considérer l'attitude du recourant comme abusive. On le peut d'autant moins que le Service des contraventions semble avoir lui-même admis l'annulation des amendes et des procédures y relatives dans un courrier du 12 octobre 2011 qu'invoque aussi le recourant. Dans ses déterminations au présent recours, ce service a confirmé que le courrier du 12 octobre 2011 concernait bien les 42 amendes infligées au recourant. Cette autorité administrative n'est cependant pas compétente pour procéder à une révision pénale.
1.8 Il résulte de ce qui précède que c'est à tort que la cour d'appel a refusé d'entrer en matière en application de l'<ref-law> et a déclaré la demande de révision irrecevable. Le recours doit être admis et la cause retournée à la cour d'appel pour qu'elle entre en matière. A noter que si la procédure de révision devait aboutir à la libération du recourant, elle impliquerait consécutivement de revoir le jugement du TAPEM.
2. Le recourant obtient gain de cause. Il ne supporte pas de frais (art. 65 al. 2 et 66 al. 1 LTF). Il peut prétendre à de pleins dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, le jugement attaqué est annulé et la cause renvoyée à la cour cantonale afin qu'elle rende une nouvelle décision au sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le Canton de Genève versera au recourant la somme de 3000 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre pénale d'appel et de révision.
Lausanne, le 12 septembre 2012
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet