Faits:
A. A.a Le 6 avril 2010, X._ a été interpellé à A._, dans le canton de Genève, en possession d'un téléphone portable qui avait été déclaré volé le 20 janvier 2010 à B._, dans le canton de Vaud. Après avoir été interrogé, il a été remis aux autorités vaudoises dans le cadre de la procédure qu'elles avaient ouvertes à la suite du vol du téléphone portable précité.
A.b Par ordonnance de condamnation du 22 avril 2010, X._ a été reconnu coupable de recel par le Ministère public du canton de Genève, qui l'a condamné à une peine pécuniaire de 20 jours-amende à 30 francs le jour, avec sursis pendant trois ans, sous déduction d'un jour-amende correspondant à un jour de détention subi avant jugement. L'intéressé a fait opposition à cette ordonnance de condamnation.
A.c Aux termes de l'ordonnance du Juge d'instruction de l'arrondissement de l'Est vaudois du 5 août 2010, X._ a bénéficié d'un non-lieu dans le cadre de la procédure ouverte dans le canton de Vaud. L'enquête avait permis d'établir que l'auteur du vol du téléphone portable était un tiers. Il était en outre indiqué que X._ s'était uniquement rendu coupable de recel. Celui-ci avait toutefois été condamné à ce titre le 22 avril 2010 par les autorités genevoises et il ne pouvait donc être condamné une seconde fois en vertu du principe ne bis in idem.
B. Par jugement du Tribunal de police de la République et canton de Genève du 24 mai 2011, rendu sur opposition de X._ à l'ordonnance de condamnation du 22 avril 2010, celui-ci a été reconnu coupable de recel (<ref-law>) et a été condamné à une peine pécuniaire de 20 jours-amende à 30 francs le jour, sous déduction de la détention avant jugement, avec sursis et délai d'épreuve de 3 ans.
C. Sur appel du condamné, la Chambre pénale d'appel et de révision de la Cour de justice de Genève a annulé cette décision par arrêt du 2 février 2012. Elle a reconnu X._ coupable de recel d'importance mineure (art. 160 ch. 1 et 172ter CP) et l'a condamné à une amende de 300 francs, la peine privative de liberté de substitution en cas de non-paiement fautif de cette amende étant de 3 jours.
D. X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut à l'annulation de la décision entreprise, à son acquittement et au renvoi de la cause à l'autorité cantonale afin qu'elle statue sur ses prétentions en indemnisation pour la détention qu'il indique avoir subie de manière injustifiée pendant 9 jours dans le cadre des procédures diligentées dans les cantons de Genève et Vaud. Il sollicite en outre l'octroi de l'assistance judiciaire.
Il n'a pas été ordonné d'échange d'écritures.

Considérant en droit:
1. Le recourant fait valoir qu'il avait invoqué l'incompétence ratione loci des autorités genevoises devant la cour cantonale, qui n'avait toutefois pas répondu à cet argument. Ce défaut de motivation constituerait un déni de justice formel (art. 29 al. 2 Cst.; 6 CEDH).
1.1 La jurisprudence a déduit du droit d'être entendu consacré à l'art. 29 al. 2 Cst. et de l'art. 6 par. 1 CEDH le devoir pour l'autorité de motiver sa décision, afin que le destinataire puisse la comprendre et la contester utilement s'il y a lieu et pour que l'autorité de recours puisse exercer son contrôle. Pour répondre à ces exigences, il suffit que le juge mentionne, au moins brièvement, les motifs qui l'ont guidé et sur lesquels il a fondé sa décision. Il n'a pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut au contraire se limiter à l'examen des questions décisives pour l'issue du litige (<ref-ruling> consid. 4.1 p. 88 et les références citées).
1.2 La cour cantonale a indiqué que le recourant n'avait pas été poursuivi dans le canton de Vaud du chef de recel, mais qu'il avait été suspecté d'avoir commis le crime préalable à cette infraction, pour laquelle il était poursuivi à Genève. Par conséquent, s'agissant du recel, le canton de Genève était le seul compétent, conformément à l'<ref-law>, qui reprenait les principes posés par l'art. 340 aCP, abrogé le 1er janvier 2011 (arrêt attaqué, consid. 1.2.1 et 1.2.3 p. 5/6). Contrairement à ce que soutient le recourant, la cour cantonale a ainsi répondu à l'argument qu'il avait soulevé portant sur la prétendue incompétence ratione loci des autorités genevoises. Une telle motivation était suffisante pour que l'intéressé comprenne la décision et puisse l'attaquer à bon escient. La cour cantonale n'a dès lors pas violé le droit du recourant à obtenir une décision motivée. Le grief doit être rejeté.
2. Le recourant fait valoir que les autorités vaudoises étaient seules compétentes ratione loci pour le juger en vertu de l'art. 350 al. 1 aCP selon lequel, lorsqu'un inculpé est poursuivi pour plusieurs infractions commises en différents lieux, l'autorité du lieu où a été commise l'infraction punie de la peine la plus grave est aussi compétente pour la poursuite et le jugement des autres infractions; si les différentes infractions sont punies de la même peine, l'autorité compétente est celle du lieu où la première instruction a été ouverte.
2.1 L'art. 350 al. 1 aCP, dans sa teneur invoquée par le recourant, a été abrogé le 1er janvier 2007, soit plus de trois ans avant les faits qui lui sont reprochés. Il n'était dès lors pas applicable en 2010, mais l'art. 344 al. 1 aCP, qui reprenait la teneur de l'art. 350 al. 1 aCP depuis le 1er janvier 2007, jusqu'à son abrogation le 1er janvier 2011.
2.2 A l'appui de son grief, le recourant fait valoir que la procédure avait d'abord été ouverte dans le canton de Vaud, où il avait été poursuivi non seulement du chef d'infraction de vol, mais également de recel. La cour cantonale a toutefois retenu - d'une manière qui lie le Tribunal fédéral (<ref-law>) - que le recourant avait été poursuivi dans le canton de Vaud pour vol uniquement, ainsi que cela ressort de l'ordonnance du 5 août 2010. Que dite ordonnance évoque aussi le recel (cf. infra consid. 3) ne signifie pas qu'une procédure pénale ait préalablement été ouverte dans le canton de Vaud à raison de cette infraction.
2.3 L'art. 350 al. 1 aCP, respectivement 344 al. 1 aCP, désigne l'autorité compétente lorsqu'un inculpé est poursuivi pour plusieurs infractions commises en différents lieux, soit dans l'hypothèse d'un concours réel (cf. Trechsel/Lieber, in : Schweizerisches Strafgesetzbuch, Praxiskommentar, 2008, n. 1 ad art. 344 aCP). L'auteur d'une infraction préalable contre le patrimoine ne peut receler les biens soustraits (<ref-ruling> consid. 1b p. 53; Bernard Corboz, Les infractions en droit suisse, vol. I, 3ème éd., 2010, n. 67 ad <ref-law>; Philippe Weissenberger, in: Basler Kommentar, Strafgesetzbuch II, 2ème éd., 2007, n. 92 ad <ref-law>). Ainsi, en l'absence de concours entre les infractions de vol et de recel, la disposition invoquée par le recourant n'était pas applicable.
Pour le surplus, le recourant ne critique pas la décision cantonale en tant qu'elle a admis, à juste titre, sa compétence sur la base de l'<ref-law>, qui reprend, avec quelques modifications d'ordre rédactionnel, l'art. 340 al. 1 aCP. En effet, selon cette disposition, l'autorité du lieu où l'acte a été commis est compétente pour la poursuite et le jugement de l'infraction; si le lieu où le résultat s'est produit est seul situé en Suisse, l'autorité compétente est celle de ce lieu. Le receleur doit être poursuivi et jugé au for désigné par sa propre action, sauf exception non réalisée en l'espèce (<ref-ruling> consid. 1 p. 148). Le recourant a été interpellé et poursuivi pour le recel dans le canton de Genève du téléphone portable volé et il ne fait pas valoir qu'il aurait également commis un acte de recel dans le canton de Vaud. La cour cantonale n'a dès lors pas violé le droit fédéral en considérant que les autorités genevoises étaient compétentes ratione loci pour le poursuivre et le condamner du chef de cette infraction.
3. Le recourant soutient qu'il avait été mis au bénéfice d'un non-lieu par les autorités vaudoises le 5 août 2010 concernant l'infraction de recel. Dès lors, en vertu du principe ne bis in idem, il ne pouvait plus être condamné par la suite pour cette même infraction par les tribunaux genevois.
3.1 Le principe ne bis in idem est un corollaire de l'autorité de chose jugée. Il appartient, selon la jurisprudence constante, au droit pénal fédéral. Il est ancré dans la Constitution fédérale (art. 8 al. 1 Cst.; cf. Michel Hottelier, in: Commentaire romand, Code de procédure pénale suisse, n. 1 ad <ref-law>) ainsi qu'à l'art. 14 al. 7 du Pacte international du 16 décembre 1966 relatif aux droits civils et politiques (RS 0.103.2) et à l'art. 4 al. 1 du Protocole n° 7 à la Convention de sauvegarde des droits de l'homme et des libertés fondamentales (RS 0.101.07). Aux termes de cette dernière disposition, nul ne peut être poursuivi ou puni pénalement par les juridictions du même État en raison d'une infraction pour laquelle il a déjà été acquitté ou condamné par un jugement définitif conformément à la loi et à la procédure pénale de cet État. Ce principe figure également, depuis le 1er janvier 2011, à l'<ref-law>.
3.2 En l'espèce, le Juge d'instruction de l'arrondissement de l'Est vaudois a prononcé un non-lieu à l'encontre du recourant aux termes de son ordonnance du 5 août 2010 au motif que l'enquête avait déterminé qu'un tiers était l'auteur du vol du téléphone portable. Il a encore indiqué que le recourant s'était rendu coupable de recel mais qu'il avait déjà été condamné pour cette infraction par le Procureur général genevois le 22 avril 2010 et qu'il ne pouvait donc être jugé une deuxième fois pour celle-ci en vertu du principe ne bis in idem.
Il a été constaté que le recourant avait été entendu dans le canton de Vaud en qualité de prévenu de vol, mais pas de recel. Il ne ressort pas de la décision attaquée que les autorités vaudoises auraient fait porter l'instruction de la cause sur les différentes conditions de réalisation de cette dernière infraction. Pour que le recourant puisse en être reconnu coupable, il ne suffisait pourtant pas qu'il ait détenu le téléphone portable volé. Il fallait encore, notamment, d'un point de vue subjectif, qu'il sache ou doive présumer, respectivement qu'il accepte l'éventualité que la chose provienne d'une infraction contre le patrimoine (cf. arrêt 6B_728/2010 du 1er mars 2011 consid. 2.2). Ainsi, en indiquant que le recourant s'était rendu coupable de recel, le Juge d'instruction vaudois n'a pas pu vouloir statuer matériellement sur cette infraction qui n'avait fait l'objet d'aucune mesure d'instruction. Il se référait uniquement à cet égard à l'ordonnance de condamnation genevoise du 22 avril 2010 qui avait retenu le recel. La mention selon laquelle le recourant ne pouvait être condamné deux fois pour la même infraction explique par ailleurs les motifs pour lesquels le Juge d'instruction vaudois ne s'est pas saisi de la question du recel. Cette indication ne signifie en revanche pas que la décision de non-lieu concernait le recel. Celle-ci porte exclusivement sur l'infraction de vol, contrairement à ce que le recourant soutient. Dès lors, en l'absence d'une décision antérieure à celle dont est recours, portant sur l'infraction de recel et disposant de l'autorité de la chose jugée, le grief de violation du principe ne bis in idem est infondé.
4. Le recourant réclame le renvoi de la cause à l'autorité cantonale afin qu'elle statue sur ses prétentions en indemnisation pour la détention préventive qu'il aurait injustement subie durant neuf jours, sur lesquelles ni les autorités vaudoises ni les autorités genevoises n'auraient statué.
Le recours est dirigé uniquement contre la décision de l'autorité cantonale genevoise. Le recourant n'est donc pas recevable à se plaindre dans le cadre de celui-ci du fait que la décision vaudoise violerait ses droits en ne statuant pas sur les prétentions qu'il invoque. De plus, la cour cantonale a considéré, à juste titre, qu'il n'appartenait pas aux autorités genevoises de l'indemniser pour la détention qu'il allègue avoir subie durant huit jours dans le cadre d'une autre procédure, conduite dans le canton de Vaud. Le recourant ne critique pas cette argumentation et il n'indique pas sur quelle base il fonde sa prétention à cet égard. La cour cantonale a par ailleurs indiqué que le recourant avait effectué un jour de détention avant jugement à Genève alors que la peine de substitution à laquelle il était condamné était de trois jours, de sorte qu'il ne pouvait prétendre à aucune indemnisation en vertu de l'<ref-law>. Le recourant n'explique pas en quoi la cour cantonale aurait violé cette disposition, ni en vertu de quelle disposition ou principe juridique il aurait droit à une indemnisation pour le jour de détention effectué à Genève dans le cadre d'une procédure à l'issue de laquelle il a été condamné. Le grief ne répond pas aux exigences de motivation de l'<ref-law> qui impose au recourant de discuter au moins brièvement les considérants de la décision litigieuse et indiquer en quoi il estime que l'autorité précédente a méconnu le droit (<ref-ruling> consid. 2.1 p. 245 s.; <ref-ruling> consid. 3.3 p. 60). Il est irrecevable.
5. Le recourant a sollicité l'octroi de l'assistance judiciaire. Comme ses conclusions étaient manifestement dénuées de chance de succès, il doit être débouté de sa demande (<ref-law> a contrario) et supporter les frais de justice, qui seront fixés en tenant compte de sa situation financière (art. 65 al. 2 et art. 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. La demande d'assistance judiciaire est rejetée.
3. Les frais judiciaires, arrêtés à 1'600 francs, sont mis à la charge du recourant.
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 6 septembre 2012
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
Le Greffier: Rieben