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.