Faits:
A. Entre le 23 août 2006 et le 20 septembre 2008, le Service des contraventions du canton de Genève a infligé à X._ 144 amendes d'ordre, d'un montant total de 8160 fr., pour des infractions à la loi sur la circulation routière. X._ n'a pas payé ces amendes, sans pour autant les contester.
B. Sur réquisition du Procureur général du canton de Genève, le Tribunal d'application des peines et mesures de ce canton a, par jugement du 9 avril 2009, converti les amendes en une peine privative de liberté de substitution de 86 jours.
Par arrêt du 22 novembre 2010, la Chambre pénale de la Cour de justice du canton de Genève a partiellement admis l'appel formé par X._. Elle a annulé le premier jugement, réduit la peine privative de liberté de substitution à 84 jours, suspendu l'exécution de cette peine et ordonné à la place un travail d'intérêt général de 336 heures.
Par arrêt du 28 mars 2011 (6B_1099/2010), le Tribunal fédéral a admis le recours de X._, annulé la décision cantonale et renvoyé la cause à l'autorité précédente pour nouvelle décision.
C. Par arrêt du 24 mai 2012, la Chambre pénale de la Cour de justice du canton de Genève a condamné X._ à une peine privative de liberté de substitution de 77 jours, suspendu l'exécution de cette peine et ordonné à la place un travail d'intérêt général de 308 heures.
D. 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 la décision entreprise en ce sens qu'il est constaté la prescription de l'ensemble des amendes visées par la procédure et, subsidiairement, à l'annulation de la décision et au renvoi de la cause à l'autorité inférieure pour nouveau jugement. Plus subsidiairement, il demande à pouvoir prouver les faits allégués. Il sollicite par ailleurs l'assistance judiciaire.
Invités à déposer des observations sur le recours, le Ministère public et la cour cantonale y ont renoncé, cette dernière se référant aux considérants de son arrêt.

Considérant en droit:
1. Le recourant invoque une violation de l'art. 109 CP et soutient que la peine relative à l'ensemble des contraventions visées par la procédure serait prescrite.
1.1 Dans son arrêt du 28 mars 2011 (6B_1099/2010), la cour de céans a exposé que la cour cantonale, qui avait statué le 22 novembre 2010, aurait dû constater que les amendes devenues exécutoires avant le 22 novembre 2007 étaient prescrites. Statuant à nouveau par arrêt du 24 mai 2012, la cour cantonale a considéré qu'elle était liée par cette date et a converti toutes les amendes devenues exécutoires postérieurement au 22 novembre 2007. Le recourant fait valoir que la prescription de la peine n'a pas cessé de courir le 22 novembre 2010, date du prononcé du premier arrêt de la cour cantonale. Selon lui, en l'absence d'un motif de suspension ou d'interruption de la prescription de la peine, la cour cantonale aurait dû constater, lorsqu'elle a statué le 24 mai 2012, que toutes les amendes devenues exécutoires avant le 24 mai 2009 étaient prescrites.
1.2 Selon la loi sur les amendes d'ordre du 24 juin 1970 (LAO; RS 741.03), les contraventions aux prescriptions fédérales sur la circulation routière peuvent être réprimées par une amende d'ordre selon une procédure simplifiée (art. 1 al. 1 LAO). La LAO ne contenant pas de normes relatives à la prescription, il convient de se référer aux règles générales du code pénal (cf. art. 104 et 333 ch. 1 CP). L'action pénale et la peine se prescrivent par trois ans (art. 109 CP). La prescription de la peine court du jour où la condamnation à l'amende devient exécutoire (art. 100 al. 1 CP applicable par renvoi de l'art. 104 CP), ce moment étant déterminé par le droit de procédure applicable (arrêt 6B_1099/2010 du 28 mars 2011 consid. 2.2 et les références citées), soit en l'occurrence le droit cantonal, les amendes infligées étant antérieures à l'entrée en vigueur du CPP.
1.3 Les 144 amendes ont été prononcées entre le 23 août 2006 et le 20 septembre 2008. Il ressort de l'arrêt attaqué que la date à laquelle les amendes sont devenues exécutoires figure au dos de chaque rapport de contravention. Le recourant ne remet pas en cause les dates ainsi établies. Le délai de prescription de la peine (3 ans) a donc commencé à courir pour chacune des amendes à la date figurant sur le rapport y relatif. Une prolongation du délai de prescription de la peine n'est possible que pour une peine privative de liberté dans les hypothèses visées à l'art. 99 al. 2 CP. Cette disposition ne prévoit aucune prolongation du délai de prescription de la peine pour une amende. La procédure de conversion de l'amende n'a pas d'influence et ne saurait permettre une prolongation du délai de prescription. En cas de conversion de peine, la prescription de celle-ci reste déterminée par la peine originelle ce qui exclut toute prolongation de la prescription pour les amendes (cf. <ref-ruling> consid. 2 p. 16 s.; YVAN JEANNERET, in Commentaire romand, Code pénal I, 2009, n° 23 ad art. 36 CP et GILBERT KOLLY, ibidem n° 26 ad art. 99 CP; DUPUIS ET AL., Petit Commentaire du Code pénal, 2012, n° 5 ad art. 36 CP). Indépendamment de l'art. 99 al. 2 CP, une prolongation de la prescription de la peine, respectivement une suspension, peut entrer en considération dans le cadre d'un recours suspensif au Tribunal fédéral qui aboutit à l'annulation de l'arrêt cantonal, la prolongation, respectivement la suspension, correspondant alors à la durée de la procédure fédérale (cf. <ref-ruling>, p. 173; TRECHSEL ET AL., Schweizerisches Strafgesetzbuch, Praxiskommentar, no 7 ad art. 99 CP; PETER MÜLLER, in Basler Kommentar, Strafrecht I, 2e éd. 2007, no 13 ad art. 99 CP). En l'espèce, le recours interjeté contre l'arrêt du 22 novembre 2010 n'était pas de plein droit suspensif selon l'art. 103 al. 2 let. b LTF dès lors que le travail d'intérêt général prononcé par l'arrêt cantonal n'entre pas dans le champ d'application de cette disposition (cf. MARC THOMMEN, in Basler Kommentar, Bundesgerichtsgesetz, 2e éd. 2011, no 21 ad art. 103 LTF). Par ailleurs, l'effet suspensif n'avait pas été accordé en application de l'art. 103 al. 3 LTF. Il s'ensuit qu'aucune prolongation de la prescription de la peine ne peut résulter de la procédure fédérale et du renvoi en instance cantonale.
Contrairement à ce qu'a retenu la cour cantonale, le délai de prescription de la peine n'a pas été définitivement interrompu le 22 novembre 2010. La cour cantonale aurait ainsi dû se placer au moment où elle a statué, soit le 24 mai 2012, pour examiner quelles amendes n'étaient pas prescrites et ne convertir que les amendes qui étaient devenues exécutoires au plus tard 3 ans avant son jugement. Tel n'était ainsi le cas que d'une seule amende, d'un montant de 80 fr., devenue exécutoire le 29 mai 2009 (cf. rapport de contravention B003425129). L'arrêt attaqué sera par conséquent annulé et la cause renvoyée à l'autorité cantonale. Il lui appartiendra de se placer au moment où elle statue pour examiner la question de la prescription de la peine en tenant compte du fait que celle-ci continue à courir, faute de prolongation du délai de prescription.
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 (art. 68 al. 1 LTF). La requête d'assistance judiciaire est sans objet (art. 64 al. 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, le jugement attaqué annulé et la cause renvoyée à l'autorité précédente pour qu'elle statue au sens des considérants.
2. Il n'est pas perçu de frais judiciaires.
3. Le Canton de Genève versera au conseil du 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 17 octobre 2012
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Juge présidant: Schneider
La Greffière: Livet