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

Considérant en droit:
1. La décision de mesures provisoires, bien qu'elle soit prise alors qu'une procédure (principale) de modification du jugement de divorce est pendante, est finale selon l'<ref-law>, car elle met fin à l'instance sous l'angle procédural (<ref-ruling> consid. 2.2 et les références citées). La décision a par ailleurs été prise en dernière instance cantonale et sur recours par le tribunal supérieur du canton de Genève (<ref-law>), dans une affaire civile non pécuniaire (<ref-law>). Le recourant, qui a qualité pour agir selon l'<ref-law>, a recouru dans le délai légal (<ref-law>).
2. L'objet du litige est en l'espèce limité à l'attribution de l'autorité parentale sur l'enfant C._, respectivement au droit de garde, chaque parent invoquant des motifs qui lui sont propres pour infirmer, respectivement confirmer, la décision attaquée et justifier de l'intérêt de l'enfant à voir l'autorité parentale octroyée à l'un ou à l'autre pour la durée de la procédure en modification du jugement de divorce.
2. L'objet du litige est en l'espèce limité à l'attribution de l'autorité parentale sur l'enfant C._, respectivement au droit de garde, chaque parent invoquant des motifs qui lui sont propres pour infirmer, respectivement confirmer, la décision attaquée et justifier de l'intérêt de l'enfant à voir l'autorité parentale octroyée à l'un ou à l'autre pour la durée de la procédure en modification du jugement de divorce.
2.1 2.1.1 Le Tribunal de première instance a retenu que le départ envisagé par la mère à New York constituait un fait nouveau important au sens de l'<ref-law>, justifiant un réexamen de l'attribution des droits parentaux. Déterminant si le déménagement était dans l'intérêt de l'enfant, le premier juge a considéré que tel n'était pas le cas. Il ressortait en effet du dossier que, suite à une procédure de divorce particulièrement longue et conflictuelle, à l'issue de laquelle les droits parentaux avaient été confiés à la mère, un équilibre avait été trouvé grâce à l'instauration d'un très large droit de visite en faveur du père, lequel voyait sa fille plusieurs jours par semaine. Les parties s'entendaient en outre à dire que C._ allait bien, qu'elle était bien intégrée dans son entourage et qu'elle suivait de manière satisfaisante son cursus scolaire. Or, le déménagement projeté, compte tenu de la distance séparant Genève de New York, modifierait de manière significative, mais négative, les éléments importants de l'équilibre de vie de la fillette, soit sa relation à son père ainsi que tout son entourage scolaire et amical. La qualité de vie de l'enfant serait en outre considérablement modifiée, le rythme de vie dans une métropole de la taille de New York étant moins adapté pour une enfant de 8 ans que le rythme de vie plus calme dont celle-ci pouvait bénéficier dans une ville comme Genève. L'autorité de première instance a également rappelé que les capacités parentales des parties avaient été jugées équivalentes et souligné que les droits parentaux avaient été attribués à la mère au regard de deux éléments, à savoir d'une part le besoin de stabilité de l'enfant, qui avait, au cours de la procédure, habité de manière prépondérante avec la défenderesse et, d'autre part, le fait que la mère semblait mieux à même de promouvoir une image positive du père. Constatant que non seulement les parties présentaient des carences évidentes sur ce dernier point, mais qu'à l'heure actuelle, le besoin de stabilité de l'enfant était également mieux préservé par l'attribution des droits parentaux au père, le magistrat en a conclu que le bien de C._ nécessitait l'attribution des droits parentaux au recourant pour la durée de la procédure. Cette solution s'imposait d'autant plus que, dans l'hypothèse où les droits parentaux seraient attribués au père à l'issue de la procédure, C._ risquerait de devoir subir deux déménagements dans un intervalle de temps relativement court, ce qui serait particulièrement déstabilisant pour elle.
2.1.2 Statuant sur appel de la mère de l'enfant, la Cour de justice a d'abord confirmé l'inscription du litige dans le contexte des mesures provisionnelles de l'<ref-law>. Relevant ensuite que tant un éventuel départ à New York que le déplacement de son lieu de vie principal de sa mère chez son père pendant la procédure se révéleraient contraires à l'intérêt de l'enfant si le jugement au fond retenait une solution inverse, la juridiction a considéré qu'il convenait d'examiner si l'issue prévisible du litige pouvait être évaluée avec une certaine fiabilité. L'autorité a néanmoins constaté, à cet égard, que la décision au fond allait essentiellement dépendre des renseignements relatifs à l'enfant, lesquels nécessitaient une instruction, le déménagement à New York ne justifiant pas, à lui seul, la modification de l'autorité parentale et de la garde dès lors qu'il ne comportait pas, en soi, une menace sérieuse pour le bien de la fillette. Dès lors qu'il était impossible d'évaluer avec une certaine fiabilité l'issue de la procédure au fond, les droits parentaux ne pouvaient être transférés au père pour la durée de la procédure, ainsi que l'avait ordonné l'autorité de première instance. Examinant si une autre mesure provisionnelle était indiquée afin de préserver l'intérêt de C._ pendant la procédure, la cour cantonale a souligné que le changement radical de lieu de vie d'un de ses parents priverait à l'évidence l'enfant du contact privilégié qu'elle entretenait avec l'autre, dont il était pourtant démontré qu'il était nécessaire à sa bonne évolution. La meilleure solution consistait ainsi à maintenir le statu quo pendant la durée de la procédure. En l'absence de menace sérieuse pour le bien de l'intéressée, il ne pouvait toutefois être fait interdiction à la mère de s'établir à New York; il convenait néanmoins de l'inviter à ne pas concrétiser son projet pendant la durée de la procédure.
3. 3.1 La loi ne définit pas l'autorité parentale. La doctrine l'appréhende comme la responsabilité et le pouvoir légal des parents de prendre les décisions nécessaires pour l'enfant mineur. Il s'agit ainsi d'un faisceau de droits et de devoirs des père et mère à l'égard de l'enfant, dont l'étendue varie en fonction de plusieurs facteurs, soit en particulier de l'âge et de la maturité de l'enfant (<ref-ruling> consid. 3.1; arrêts 5A_497/2011 du 5 décembre 2011 consid. 2.1.2 et les références; 5A_643/2011 du 23 novembre 2011 consid. 5.1.2). Le droit de garde est une composante de l'autorité parentale. Il comprend en particulier la faculté de déterminer le lieu de résidence et le mode d'encadrement de l'enfant (<ref-ruling> consid. 4a; <ref-ruling> consid. 2 et les références). En cas de vie séparée des père et mère, le domicile légal de l'enfant se trouve auprès de celui des parents auquel le droit de garde a été attribué (<ref-law>).
Le titulaire unique du droit de garde peut donc, sous réserve de l'abus de droit - par exemple s'il n'a pas de motif plausible ou si son seul but est de rendre plus difficiles les relations entre l'enfant et l'autre parent -, déménager à l'étranger avec l'enfant sans l'accord de l'autre parent, le droit de visite devant alors être adapté en conséquence. En cas de menace sérieuse pour le bien de l'enfant, l'autorité tutélaire - respectivement le juge des mesures protectrices ou provisoires (cf. <ref-law>) - peut toutefois interdire le départ à l'étranger, en se fondant sur l'<ref-law>; le juge peut également attribuer l'autorité parentale à l'autre parent (<ref-ruling> consid. 3.3). En l'absence du prononcé de telles mesures, le parent seul titulaire du droit de garde ne se rend coupable d'aucune infraction en s'installant à l'étranger; le parent qui ne bénéficie pas du droit de garde n'a, quant à lui, pas qualité pour former une demande de retour au sens de la Convention de La Haye sur les aspects civils de l'enlèvement international d'enfants du 25 octobre 1980 (<ref-ruling> consid. 3.4 et 3.5).
Le titulaire unique du droit de garde peut donc, sous réserve de l'abus de droit - par exemple s'il n'a pas de motif plausible ou si son seul but est de rendre plus difficiles les relations entre l'enfant et l'autre parent -, déménager à l'étranger avec l'enfant sans l'accord de l'autre parent, le droit de visite devant alors être adapté en conséquence. En cas de menace sérieuse pour le bien de l'enfant, l'autorité tutélaire - respectivement le juge des mesures protectrices ou provisoires (cf. <ref-law>) - peut toutefois interdire le départ à l'étranger, en se fondant sur l'<ref-law>; le juge peut également attribuer l'autorité parentale à l'autre parent (<ref-ruling> consid. 3.3). En l'absence du prononcé de telles mesures, le parent seul titulaire du droit de garde ne se rend coupable d'aucune infraction en s'installant à l'étranger; le parent qui ne bénéficie pas du droit de garde n'a, quant à lui, pas qualité pour former une demande de retour au sens de la Convention de La Haye sur les aspects civils de l'enlèvement international d'enfants du 25 octobre 1980 (<ref-ruling> consid. 3.4 et 3.5).
3.2 3.2.1 A la requête du père ou de la mère de l'enfant ou de l'autorité tutélaire, l'attribution de l'autorité parentale doit être modifiée lorsque des faits nouveaux importants l'exigent pour le bien de l'enfant (<ref-law>). Une modification dans l'attribution de l'autorité parentale ne dépend toutefois pas seulement de l'existence de circonstances nouvelles importantes; elle doit aussi être commandée par le bien de l'enfant (arrêts 5A_63/2011 du 1er juin 2011 consid. 2.4.1; 5A_697/2009 du 4 mars 2010 consid. 3.1 et les nombreuses références). Ainsi, lorsque le parent titulaire du droit de garde envisage de déménager, l'autre parent peut agir en modification du jugement de divorce et conclure à ce que l'autorité parentale et, en conséquence, le droit de garde, lui soient transférés si le déplacement projeté n'est pas dans l'intérêt de l'enfant (cf. arrêts 5C.19/2002 du 15 octobre 2002 consid. 3 publié in: FamPra.ch 2003 445 ss; 5A_483/2011 du 31 octobre 2011 consid. 3 publié in: FamPra.ch 2012 206; LEUBA/BASTONS BULLETTI, in: Commentaire romand, Code civil I, 2010, n. 4 ad <ref-law>; BÜCHLER/WIRZ, in: FamKommentar, Band I, 2e éd. 2011, n. 17 ad <ref-law>).
3.2.2 Des mesures provisionnelles peuvent être prises pour la durée de la procédure de modification du jugement de divorce. Celles-ci doivent non seulement tenir compte des implications qu'entraînent les circonstances de fait nouvelles sur le bien de l'enfant, mais visent également à maintenir l'objet du litige dans l'état où il se trouve pendant la durée du procès et, ainsi, à assurer l'exécution ultérieure du jugement au fond. Or, à supposer que cette dernière décision modifie l'attribution de l'autorité parentale, le déplacement de l'enfant à l'étranger durant la procédure pourrait compromettre son exécution: un départ pour un État tiers entraîne en effet un changement de résidence et, ainsi, l'incompétence des juridictions suisses. Les mesures provisionnelles prononcées dans ce contexte doivent par conséquent assurer le maintien du lieu de résidence de l'enfant en Suisse jusqu'à l'issue de la procédure, à moins que la demande n'apparaisse d'emblée irrecevable ou manifestement infondée.
3.3 En l'espèce, le juge du divorce a attribué l'autorité parentale à la mère, sous la réserve qu'elle ne quitte pas la Suisse. Vu le déménagement envisagé, le recourant était par conséquent fondé à introduire une action en modification du jugement de divorce et à solliciter le prononcé de mesures provisionnelles pour la durée de cette procédure.
3.3.1 Contrairement à ce que paraît penser l'intimée, il ne s'agit pas ici de préserver l'attribution de l'autorité parentale décidée par le juge du divorce, mais bien de maintenir la résidence de l'enfant en Suisse jusqu'à droit connu sur la décision au fond, afin d'en assurer l'exécution. Cette exigence s'impose en l'espèce dès lors que l'action en modification du jugement de divorce introduite par le père et par laquelle celui-ci sollicite l'attribution des droits parentaux n'est pas dépourvue de toute chance de succès: au cours de la procédure de mesures protectrices de l'union conjugale, puis dans le cadre de la procédure de divorce au fond, il a été souligné par les experts, puis par les magistrats, que, dans l'hypothèse où la mère quitterait Genève, une éventuelle modification de l'attribution des droits parentaux devait être réservée; l'intéressée a en l'espèce pris la décision concrète de partir s'installer à New York avec les conséquences qu'une telle résolution implique sur le très large droit de visite dont dispose le père de l'enfant, élément que les autorités cantonales successives ont retenu comme étant l'un des garants de la stabilité de l'enfant.
3.3.2 Or, la décision attaquée ne permet nullement le maintien de la résidence de l'enfant à Genève. Bien qu'elle ait souligné les impacts négatifs d'un déplacement à New York, puis mis en évidence la stabilité trouvée par l'enfant à Genève et l'importance d'éviter une modification de son cadre de vie avant l'issue de la procédure au fond, la cour cantonale a étonnamment considéré que le déménagement projeté par la mère ne comportait pas, en soi, une menace pour le bien de C._; inviter l'intimée à renoncer à son projet suffisait dès lors à garantir la présence de l'enfant à Genève, sans qu'une modification de l'attribution des droits parentaux, décidée en première instance, n'ait à intervenir, ni qu'il se justifie d'interdire à la mère de concrétiser son projet.
Force est toutefois de constater que l'invitation formulée à l'adresse de l'intimée ne dispose d'aucune force juridique contraignante, l'intéressée pouvant ainsi parfaitement décider de matérialiser son projet et de s'installer à New York, compromettant ainsi l'exécution de la procédure à rendre au fond. Seules deux mesures sont susceptibles d'assurer la présence de l'enfant à Genève: d'une part, le maintien des droits parentaux à la mère, assortie toutefois de l'interdiction d'emmener l'enfant à New York dans l'intention d'y établir sa résidence et de l'ordre de restituer les passeports et le permis d'établissement de C._; d'autre part, l'attribution de l'autorité parentale et, par conséquent, du droit de garde au père, conformément à la solution retenue par le premier juge - la fillette s'est en effet installée chez son père depuis le 9 mars 2012, en exécution du jugement de première instance et suite aux ordonnances du Tribunal de céans des 18 avril, 26 avril, 1er, 18 et 29 mai 2012 privilégiant le maintien de cette solution en raison du risque de départ.
Depuis la séparation des parties en 2005, si son père exerçait certes un large droit de visite, C._ a néanmoins toujours vécu chez sa mère. Les parties ne contestent pas que cette solution a fonctionné à satisfaction et permis d'assurer un cadre stable à l'enfant, après une procédure de divorce particulièrement longue et conflictuelle; il convient donc de privilégier cette solution, le maintien de l'enfant dans un cadre qui s'est révélé stabilisant et conforme à son bien-être étant assuré par la mesure interdisant le déménagement envisagé pour la durée de la procédure au fond.
4. En définitive, le recours est partiellement admis et l'arrêt attaqué est réformé en ce sens qu'il est interdit à l'intimée de déménager avec C._ à New York pendant la durée de la procédure de modification du jugement de divorce introduite par le recourant et qu'il lui est ordonné de remettre sans délai au père le passeport américain, le passeport anglais et le permis d'établissement suisse de C._. Les frais judiciaires sont mis pour moitié à la charge du recourant et pour moitié à celle de l'intimée (<ref-law>), les dépens étant compensés (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est partiellement admis et l'arrêt réformé en ce sens qu'il est interdit à Dame X._ d'emmener sa fille C._ à New York dans l'intention d'y établir sa résidence et qu'il lui est ordonné de remettre sans délai à X._ le passeport américain, le passeport anglais et le permis d'établissement suisse de C._.
2. Les frais judiciaires, arrêtés à 5'000 fr., sont mis pour moitié à la charge du recourant et pour moitié à la charge de l'intimée.
3. Les dépens sont compensés.
4. La cause est renvoyée à la Cour de justice du canton de Genève pour nouvelle décision sur les frais et dépens des instances cantonales.
5. Le présent arrêt est communiqué aux parties, à la Cour de justice du canton de Genève, Chambre civile, et au Tribunal tutélaire du canton de Genève.
Lausanne, le 10 août 2012
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Hohl
La Greffière: de Poret Bortolaso