Faits: A. X._, né le *** 1965, et Dame X._, née le *** 1969, ont contracté mariage le 19 mars 2003 aux États-Unis. Dame X._ a deux enfants issus d'une précédente union: A._, né le *** 1992, et B._, née le *** 1997. Ceux-ci ont vécu avec les époux X._ dès l'été 2003 jusqu'en avril 2005, date à laquelle leur mère a décidé de transférer leur domicile à Londres auprès de leur père. B._ est néanmoins revenue vivre avec sa mère en été 2010; quant à A._, désormais majeur, il vit actuellement à Z._. Dame X._ et X._ ont une fille, C._, née le *** 2004 à Genève. Le couple s'est séparé le 29 juin 2005. Les parties réclament chacune l'attribution de l'autorité parentale exclusive et, en conséquence, le droit de garde sur leur fille C._. B. B.a Par jugement du 2 août 2006, rendu sur mesures protectrices de l'union conjugale, le Tribunal de première instance du canton de Genève (ci-après Tribunal de première instance) a attribué l'autorité parentale et la garde de C._ à sa mère, son père se voyant réserver un large droit de visite de 5 jours consécutifs par mois et la moitié des vacances scolaires. Une curatelle d'assistance éducative ainsi qu'une curatelle d'organisation et de surveillance du droit de visite a été ordonnée. Les experts psychologues consultés dans le cadre de dite procédure ont conclu à l'attribution de la garde de l'enfant à la mère, remarquant toutefois que, si celle-ci devait décider de déménager, cette solution devait être revue. B.b Le divorce des époux X._ a été prononcé par jugement du 5 juin 2008. L'autorité parentale et la garde de la fillette ont été attribuées au père, la mère disposant d'un droit de visite d'une semaine sur deux et la moitié des vacances scolaires. La curatelle d'organisation et de surveillance des relations personnelles a été maintenue. Statuant le 16 janvier 2009 sur appel de la mère, la Cour de justice a partiellement annulé le jugement de première instance et attribué à l'intéressée l'autorité parentale et le droit de garde sur C._, un droit de visite d'un week-end sur deux, d'une semaine sur deux du mardi soir après l'école au jeudi matin avant l'école ainsi que la moitié des vacances scolaires et jours fériés étant réservé au père. La curatelle d'organisation du droit de visite a été maintenue. Les juges cantonaux ont rappelé que, si la mère devait quitter Genève, l'attribution des droits parentaux pourrait être sujette à modification, ainsi que l'avaient évoqué les experts judiciaires amenés à intervenir dans le cadre de la procédure de mesures protectrices de l'union conjugale. Saisi d'un recours du père de l'enfant, le Tribunal fédéral a jugé que la cour cantonale n'avait pas violé le droit fédéral en attribuant l'autorité parentale et la garde de l'enfant à sa mère (arrêt 5A_127/2009 du 12 octobre 2009 consid. 3). C. C.a Le 12 janvier 2012, X._ a déposé devant le Tribunal de première instance une action en modification du jugement de divorce du 5 juin 2008, avec demande de mesures superprovisionnelles et provisionnelles. A l'appui de son action, l'intéressé exposait que son ex-épouse avait l'intention de s'installer à New York avec C._ dès juin 2012, afin de rejoindre son nouvel ami. Cette information a été confirmée en audience par la mère, celle-ci précisant toutefois qu'elle envisageait de prendre un appartement séparé de celui de son ami; il était prévu que B._ et A._ déménagent également, seule B._ faisant toutefois ménage commun avec elle. Dame X._ a également indiqué avoir des projets pour travailler à 50% en tant qu'architecte d'intérieur et prévoir d'inscrire C._ dans une école publique de Greenwich Village. C.b Sur le fond, X._ a notamment conclu à l'attribution de l'autorité parentale et du droit de garde sur sa fille, un large droit de visite étant réservé à sa mère, ainsi qu'à la suppression de la contribution d'entretien due en faveur de sa fille et à la condamnation de son ex-épouse au paiement des charges liées aux besoins courants de C._ pendant l'exercice de son droit de visite. C.c C.c.a X._ a pris les mêmes conclusions sur mesures provisionnelles, sous réserve du droit de visite, dont il exige qu'il s'exerce uniquement en Suisse. L'intéressé a également conclu à ce que le Tribunal ordonne à son ex-épouse, sous la menace de la peine prévue par l'art. 292 CPC, de lui remettre immédiatement les passeports américain et anglais de l'enfant ainsi que son permis d'établissement suisse et autorise au besoin la saisie par la force publique des documents d'identité de l'enfant. A titre subsidiaire, il a conclu à ce que le Tribunal fasse interdiction à la mère de quitter la Suisse avec l'enfant. La requête de mesures superprovisionnelles a été rejetée par ordonnance du 13 janvier 2012, le père n'ayant pas rendu vraisemblable l'existence d'une urgence particulière justifiant le prononcé de mesures avant audition des parties. Statuant sur mesures provisionnelles le 6 mars 2012, le Tribunal de première instance a fait droit à la requête de X._, lui attribuant notamment l'autorité parentale et le droit de garde sur sa fille C._ (ch. 2). Un droit de visite était réservé à Dame X._ tant dans l'hypothèse où elle demeurait à Genève que dans celle où elle déménageait à New York (ch. 3 et 4) et la curatelle d'organisation et de surveillance du droit de visite était maintenue (ch. 5). Ordre était en outre donné à la mère de remettre au père les passeports américain et anglais de l'enfant ainsi que son permis d'établissement (ch. 6). C.c.b Dame X._ a fait appel de ce jugement, en sollicitant l'effet suspensif. Celui-ci a été accordé par la Cour de justice le 3 avril 2012. Saisi d'un recours du père de l'enfant, le Tribunal fédéral, par trois ordonnances successives (affaire 5A_280/2012 des 18 avril, 26 avril et 1er mai 2012), a jugé qu'il y a avait lieu de maintenir les choses en l'état durant la procédure fédérale, la fillette demeurant par conséquent sous la garde de son père auprès duquel elle s'était établie suite à l'ordonnance de mesures provisionnelles du 6 mars 2012. Par arrêt du 8 mai 2012, la Cour de justice a notamment annulé les ch. 2 à 6 de l'ordonnance attaquée, invitant toutefois Dame X._ à ne pas déménager avec sa fille pendant la durée de la procédure et ordonnant à X._ de restituer à son ex-épouse le passeport américain et le permis d'établissement de sa fille. Les parties étaient, pour le surplus, déboutées de toutes autres conclusions. D. Agissant par la voie du recours en matière civile le 17 mai 2012, X._ conclut à l'annulation de l'arrêt rendu par la Cour de justice le 8 mai 2012 et sollicite, à titre principal, la confirmation de l'ordonnance sur mesures provisionnelles rendue par le Tribunal de première instance le 6 mars 2012, étant précisé que le droit de visite de la mère doit s'exercer exclusivement en Suisse et que la contribution à l'entretien de l'enfant dont il est débiteur est supprimée; subsidiairement, il réclame le renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des considérants. L'intimée conclut au rejet du recours et à la confirmation de l'arrêt attaqué; la cour cantonale se réfère aux considérants de cette dernière décision. Les parties ont chacune déposé des observations complémentaires. E. Par ordonnance présidentielle du 18 mai 2012, l'effet suspensif a été octroyé à titre superprovisoire. Le 29 mai 2012, la Présidente de la Cour de céans a attribué le bénéfice de l'effet suspensif au recours en ce sens que l'enfant demeure sous la garde de son père pendant la durée de la procédure devant le Tribunal fédéral, les mesures superprovisoires ordonnées le 18 mai 2012 étant ainsi maintenues.