Faits:
A. A.a Par acte notarié du 18 octobre 1986, C._ et D._ ont vendu aux époux B._, à raison de la moitié chacun, une surface de 300 m2 non construite, à distraire de la parcelle no 121, sise sur la commune de X._. Les biens-fonds issus de la division portent les nos 121 et 121a, ce dernier article devenant propriété des époux B._.
Selon l'acte notarié, les vendeurs ont constitué trois servitudes à charge du solde de leur parcelle, dont une servitude réelle de passage à véhicules. L'assiette de cette servitude figurait sur un plan, annexé à l'acte et signé par les parties le 17 octobre 1986. Selon ledit plan, la servitude permettait d'accéder à la parcelle no 121a en longeant la limite nord de la parcelle no 121.
Le notaire en charge de l'instrumentation de l'acte de vente a adressé au Registre foncier l'acte signé par les parties, accompagné d'un plan de situation établi par le géomètre officiel et daté du 7 novembre 1986, sur lequel il a lui-même reporté l'assiette des trois servitudes, mais de façon inexacte: ainsi, selon ce plan, le tracé de la servitude de passage à véhicules ne permettait pas de rejoindre la parcelle no 121a. C'est ce dernier plan, non signé par les parties et qui ne leur a d'ailleurs jamais été soumis, qui se trouve au Registre foncier.
A.b Le 6 septembre 1989, C._ et D._ ont vendu aux époux E._ les parcelles nos 121, 122a et 209. L'acte notarié prévoyait que, "dans la mesure où la servitude de passage pour véhicules (...) peut être radiée, le notaire procédera à ladite radiation (...)". A l'occasion de la signature de cet accord, les vendeurs ont indiqué aux époux E._ l'assiette des différentes servitudes.
Invités à se prononcer sur la radiation de la servitude de passage pour véhicules dont leur parcelle bénéficiait, les époux B._ ont refusé d'y renoncer.
A.c Le 12 octobre 2005, les époux E._ ont vendu les articles nos 121, 122a et 209 aux époux A._. Deux jours plus tôt, les époux B._ avaient informé les nouveaux acquéreurs de l'existence de la servitude de passage à véhicules dont leur parcelle bénéficiait sur l'immeuble no 121 et leur avaient présenté les pièces établissant leur droit.
Différentes discussions sont alors intervenues entre les époux B._ et A._ quant à l'assiette de la servitude contestée. Les consorts A._ ont finalement annoncé aux époux B._ vouloir poser une barrière afin d'empêcher le passage auquel ils prétendaient.
A.d Le 21 mars 2006, les époux B._ ont ainsi saisi le juge des districts d'Hérens et Conthey d'une requête de mesures provisionnelles tendant à faire interdiction aux époux A._ d'empêcher l'exercice de la servitude de passage à véhicules.
Leur requête a été rejetée par décision du 30 mai 2006.
B. Par demande du 18 août 2006, les époux B._ ont ouvert action à l'encontre des époux A._ devant le juge des districts d'Hérens et Conthey. Les demandeurs concluaient principalement à ce que le Registre foncier de Sion rectifie l'inscription de la servitude de passage à véhicules litigieuse conformément au plan du 17 octobre 1986 et, subsidiairement, à ce qu'il soit constitué, contre indemnité, une servitude de passage à véhicules à charge de la parcelle no 121 et en faveur du bien-fonds no 121a, selon l'assiette définie par le tracé actuel de la route existante.
Le dossier a été transmis au Tribunal cantonal du canton du Valais. Par jugement du 13 novembre 2009, la Cour civile II a admis l'action en rectification interjetée par les époux B._.
C. Contre cette décision, les époux A._ déposent, le 15 décembre 2009, un "recours en matière civile et violation des droits constitutionnels" au Tribunal fédéral. Les recourants concluent à l'admission de leur recours, à l'annulation du jugement attaqué et à ce que celui-ci soit réformé en ce sens qu'il soit constaté que leur partie adverse n'est pas au bénéfice d'une servitude de passage à véhicules, subsidiairement à ce qu'ils soient mis au bénéfice de la bonne foi du Registre foncier. A l'appui de leurs conclusions, les recourants invoquent la violation des art. 973 et 975 CC ainsi que la violation de l'interdiction de l'arbitraire.
Les intimés n'ont pas été invités à répondre.

Considérant en droit:
1. 1.1 La décision attaquée est une décision finale (<ref-law>), rendue en matière civile (art. 72 al. 1), par l'autorité cantonale de dernière instance (<ref-law>), dans une affaire dont la valeur litigieuse de 30'000 fr. est atteinte (<ref-law>). Le recours a par ailleurs été interjeté dans le délai prévu par la loi (<ref-law>), par les parties qui ont succombé dans leurs conclusions devant l'instance précédente (<ref-law>), de sorte que le recours en matière civile est recevable, à l'exclusion du recours constitutionnel subsidiaire.
1.2 Les recourants méconnaissent que le choix entre la voie du recours en matière civile et celle du recours constitutionnel subsidiaire dépend de la nature de l'affaire et, si elle est pécuniaire, de la valeur litigieuse (AF 133 III 446 consid. 3.1 p. 448), ainsi que, exceptionnellement, de l'existence d'une question juridique de principe (<ref-law>). Le grief d'arbitraire dans l'appréciation des preuves (art. 9 Cst.), invoqué dans le recours constitutionnel subsidiaire, sera donc traité dans le recours en matière civile, dont les conditions de recevabilité sont remplies.
2. 2.1 Saisi d'un recours en matière civile, le Tribunal fédéral applique en principe le droit d'office (<ref-law>). Il n'examine toutefois les griefs de violation des droits constitutionnels, et notamment la violation de l'interdiction de l'arbitraire, que s'ils sont invoqués et motivés par le recourant (<ref-law>), c'est-à-dire s'ils ont été expressément soulevés et exposés de façon claire et détaillée. Pour de tels griefs, l'exigence de motivation correspond à celle qui résultait de l'art. 90 al. 1 let. b OJ pour le recours de droit public (<ref-ruling> consid. 6; 639 consid. 2; <ref-ruling> consid. 1.4). Le recourant qui se plaint d'arbitraire ne saurait dès lors se contenter d'opposer sa thèse à celle de la juridiction cantonale, mais doit démontrer, par une argumentation précise, que cette décision repose sur une application de la loi ou une appréciation des preuves manifestement insoutenables. Les critiques de nature appellatoire sont irrecevables (cf. <ref-ruling> consid. 4.1; <ref-ruling> consid. 1.3 et les arrêts cités).
2.2 Le Tribunal fédéral ne peut s'écarter des faits établis par l'autorité précédente que si ceux-là ont été établis de façon manifestement inexacte ou en violation du droit au sens de l'<ref-law> (<ref-law>) et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>). Le recourant qui soutient que les faits ont été établis d'une manière manifestement inexacte (<ref-law>), à savoir arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.4.1 p. 39; <ref-ruling> consid. 1.2.2 p. 252), doit démontrer, par une argumentation précise, en quoi consiste la violation; le Tribunal fédéral n'examine en effet la violation de l'interdiction de l'arbitraire que si un tel grief a été invoqué et motivé par le recourant (<ref-law>; consid. 2.1 supra).
3. 3.1 Aux termes de l'<ref-law>, tout droit dont la constitution est légalement subordonnée à une inscription au Registre foncier, n'existe comme droit réel que si cette inscription a eu lieu. Le second alinéa précise que l'étendue d'un droit peut être précisée, dans les limites de l'inscription, par les pièces justificatives ou de toute autre manière. Lex specialis en matière de servitudes, l'<ref-law> reprend cette dernière disposition en prévoyant que l'inscription fait règle en tant qu'elle désigne clairement les droits et les obligations dérivant de la servitude (al. 1). L'étendue de celle-ci peut être précisée, dans les limites de l'inscription, soit par son origine, soit par la manière dont la servitude a été exercée pendant longtemps, paisiblement et de bonne foi (al. 2). Pour déterminer le contenu d'une servitude, il convient ainsi de procéder selon l'ordre des étapes prévu par l'<ref-law>: le juge doit dès lors se reporter en priorité à l'inscription au Registre foncier, c'est-à-dire à l'inscription au feuillet du grand livre; ce n'est que si celle-ci est peu claire, incomplète ou sommaire, que la servitude doit être interprétée selon son origine, à savoir l'acte constitutif déposé comme pièce justificative au Registre foncier (<ref-ruling> consid. 3.1; <ref-ruling> consid. 2a; arrêt 5C.126/2004 du 21 octobre 2004 consid. 2.3 in RNRF 2005 307). Le contrat de servitude et le plan sur lequel est reportée l'assiette de la servitude constituent à cet égard des pièces justificatives (<ref-law>). Si le titre d'acquisition ne permet pas de déterminer le contenu de la servitude, l'étendue de celle-ci peut alors être précisée par la manière dont elle a été exercée paisiblement et de bonne foi (<ref-law>).
3.2 Dans le domaine du principe absolu de l'inscription (<ref-law>), la règle de l'inscription est tenue en échec par le principe de la légalité (ou de la causalité), principe que la jurisprudence déduit de l'<ref-law> (ATF 64 II 284 consid. 2a; cf. également PAUL-HENRI STEINAUER, tome I, 4e éd., 2007, n. 138; Henri Deschenaux, Le Registre foncier, in: Traité de droit privé suisse, volume 5, tome II/2, 1983, p. 599; Arthur Homberger, Zürcher Kommentar, 1938, n. 3 ad <ref-law>). Aux termes de cette dernière disposition, l'inscription est faite indûment lorsqu'elle a été opérée sans droit ou en vertu d'un acte juridique non obligatoire. L'inscription constitutive est indue chaque fois qu'il manque l'une de ses deux conditions matérielles, à savoir un titre juridique valable (acte générateur d'obligations) et une réquisition émanant de la personne compétente (acte de disposition; Steinauer, n. 908; Deschenaux, op. cit., p. 599 ss; Homberger, op. cit., n. 3 ad <ref-law>). Est ainsi indue l'inscription opérée sur la base d'une vente nulle en raison d'un vice de forme ou invalidée pour vice de la volonté; l'absence de réquisition d'inscription ou le vice de la volonté dont celle-ci est entachée rendent aussi indue l'opération effectuée (Deschenaux, op. cit., p. 600; Homberger, op. cit., n. 8 ad <ref-law> et les références; Fritz Ostertag, Berner Kommentar, 1912, n. 10 ad <ref-law>; STEINAUER, n. 909). Le redressement d'une inscription opérée indûment au Registre foncier peut être obtenu par l'action en rectification du Registre foncier (<ref-law>; <ref-ruling> consid. 4a; <ref-ruling> consid. 3.1.1; DESCHENAUX, op. cit., p. 661; STEINAUER, n. 954 s.).
3.3 L'inscription indue ne produit pas d'effets, sous réserve de la protection de l'acquéreur de bonne foi (<ref-law>). Ainsi, elle ne produit pas d'effets entre les parties initiales, à savoir les personnes directement impliquées dans le rapport juridique (Steinauer, n. 914; DESCHENAUX, op. cit., p. 591), ni à l'égard des tiers qui savent qu'elle est indue ou qui auraient dû le savoir. Ces "tiers de mauvaise foi" ne peuvent invoquer l'inscription indue (<ref-law>) et contre eux, celui dont les droits réels sont lésés par l'inscription peut invoquer directement l'irrégularité de celle-ci (<ref-law>; STEINAUER, n. 915; HOMBERGER, n. 10 ss ad art. 974).
Si la bonne foi du tiers acquéreur est présumée (<ref-law>), celui-ci est toutefois déchu du droit de l'invoquer si elle est incompatible avec l'attention que les circonstances permettaient d'exiger de lui (<ref-law>).
4. 4.1 En l'espèce, la cour cantonale a retenu que l'inscription au Registre foncier faisait état, entre autres, d'une servitude de passage pour véhicules. Elle a ensuite examiné si les pièces justificatives, et en particulier le plan annexé à l'inscription, contenaient une inexactitude dès le départ. Appréciant les déclarations de C._, D._ et Me Y._ - notaire ayant instrumenté l'acte notarié prévoyant la constitution des servitudes -, les juges cantonaux ont retenu que la volonté réelle des parties au contrat de servitude était de créer une servitude de passage en voiture, permettant aux propriétaires de la parcelle 121a d'accéder de façon motorisée à leur terrain. La juridiction cantonale en a dès lors déduit que le plan déposé au Registre foncier, daté du 7 novembre 1986, ne correspondait pas à la volonté des parties puisque la servitude de passage à véhicules qui y avait été reportée ne se prolongeait pas jusqu'à la parcelle 121a, contrairement au plan qu'elles avaient signé le 17 octobre 1986. L'action en rectification du Registre foncier était en conséquence ouverte aux recourants.
4.1.1 Les recourants contestent avant tout l'appréciation que la cour cantonale a donnée à la volonté réelle des parties au contrat constitutif de servitude. Ils se limitent alors à la qualifier de fausse, d'inexacte et d'arbitraire, estimant qu'elle serait contraire à la réalité, aux pièces du dossier et aux témoignages, notamment à celui de E._. Par leur critique, les recourants ne s'en prennent cependant nullement à la motivation de la cour cantonale, ni aux faits déterminants, à savoir la volonté réelle des parties au contrat de servitude telle qu'elle résulte des déclarations sur lesquelles s'est fondée la cour cantonale. Appellatoire, elle est dès lors irrecevable (consid. 2.1 supra).
Au contraire des juges cantonaux, les recourants prétendent ensuite que le plan du 7 novembre 1986 correspondrait exactement à la volonté des parties, contrairement au plan du 17 octobre 1986, qui n'avait d'ailleurs jamais été inscrit au Registre foncier. Or, les recourants ne sauraient remettre en cause la conclusion cantonale dans la mesure où celle-ci constitue la conséquence logique de l'appréciation de la volonté réelle des parties, dont ils ne sont pas parvenus à démontrer l'arbitraire.
Les recourants affirment également que les intimés n'auraient jamais exercé leur servitude comme mentionné dans le plan du 17 octobre 1986: s'ils avaient utilisé sporadiquement le milieu de la parcelle no 121, ils n'auraient jamais utilisé la prétendue servitude pour le motif qu'elle serait impraticable et demanderait des aménagements importants. Les recourants ne démontrent cependant pas en quoi cet élément de fait aurait une influence quelconque sur le sort de l'action, de sorte qu'il n'y a pas lieu d'entrer en matière sur cette critique (consid. 2.2 supra).
4.1.2 Les recourants reprochent aussi à la cour cantonale d'avoir violé l'<ref-law>. Leurs critiques se fondent toutefois sur des faits qui ne sont pas ceux retenus et dont ils ne sont pas parvenus à démontrer qu'ils auraient été arbitrairement établis par la juridiction cantonale: il en est ainsi lorsqu'ils prétendent que le plan du 7 novembre 1986 correspondrait exactement à la volonté des parties ou lorsqu'ils soutiennent que les intimés n'auraient jamais utilisé le droit de passage tel que mentionné dans le plan du 17 octobre 1986. En affirmant enfin de façon péremptoire que seule l'inscription au Registre foncier ferait foi et non pas la "pseudo-volonté" des parties, ils ignorent la portée du principe de causalité tiré de l'<ref-law> (cf. supra 3.2), lequel permet précisément d'ouvrir action en rectification du Registre foncier lorsqu'une réquisition d'inscription est entachée d'une erreur.
4.2 Dans un second temps, la cour cantonale a examiné si les recourants pouvaient être admis à exciper de leur bonne foi (<ref-law>), voire de celle des époux E._, circonstance permettant de rejeter l'action en rectification du Registre foncier.
Les juges cantonaux ont alors observé que, peu avant d'acquérir la parcelle no 121, les recourants avaient eu une discussion avec les intimés au sujet de l'assiette de la servitude de passage pour véhicules et, qu'à cette occasion, les intimés avaient montré à leurs futurs voisins les documents en leur possession. Il apparaissait dès lors exclu que les intimés n'eussent pas fait état du plan du 17 octobre 1986 et de ses divergences avec celui déposé au Registre foncier. Le tribunal cantonal a par ailleurs noté que l'assiette de la servitude de passage telle que dessinée sur le plan du 7 novembre 1986 ne correspondait à aucun besoin et que l'assiette de la servitude était visible sur le terrain, les intimés ayant aménagé un accès en empierrant le tracé. Au vu de ces circonstances douteuses, les recourants ne pouvaient se contenter de se fier au plan déposé au Registre foncier et ne pouvaient en conséquence invoquer leur bonne foi. L'instance précédente a également jugé que les recourants ne pouvaient non plus se prévaloir de la bonne foi des époux E._, dans la mesure où, lorsque ceux-ci avaient acheté la parcelle no 121, ils avaient été informés de l'existence d'une servitude permettant aux propriétaires de la parcelle no 121a d'accéder en voiture jusqu'à leur chalet.
4.2.1 Les recourants prétendent au contraire qu'ils seraient de bonne foi et qu'ils devraient en conséquence être mis au bénéfice de l'<ref-law>, réaffirmant que les intimés ne traverseraient la parcelle no 121 que depuis quelque temps seulement et soutenant que les époux E._ leur auraient garanti qu'il n'existait aucun droit de passage à l'exception de ceux mentionnés au Registre foncier selon le plan du 7 novembre 1986. A nouveau, les recourants ne contestent nullement l'appréciation cantonale constatant leur absence de bonne foi et n'en démontrent par conséquent aucunement l'arbitraire. Leurs critiques sont donc irrecevables.
4.2.2 En conclusion, il résulte de l'appréciation des preuves que la réquisition d'inscription était indue dès lors qu'elle ne correspondait pas à la volonté réelle des parties, soit plus précisément au titre d'acquisition et au plan signé par les parties au contrat constitutif de servitudes. Les recourants ne pouvant en outre se prévaloir de leur bonne foi, c'est donc à bon droit que la cour cantonale a admis l'action en rectification du Registre foncier et déclaré que le plan du 17 octobre 1986 devait être conservé à titre de pièce justificative.
5. Le recours constitutionnel subsidiaire est irrecevable; le recours en matière civile est rejeté, dans la mesure de sa recevabilité. Les frais judiciaires sont mis à la charge des recourants qui succombent (<ref-law>). Aucune indemnité de dépens n'est octroyée aux intimés qui ne se sont pas déterminés.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours constitutionnel subsidiaire est irrecevable.
2. Le recours en matière civile est rejeté dans la mesure où il est recevable.
3. Les frais judiciaires, arrêtés à 3'000 fr., sont mis solidairement à la charge des recourants.
4. Le présent arrêt est communiqué aux parties et à la Cour civile II du Tribunal cantonal du canton du Valais.
Lausanne, le 12 mars 2010
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl de Poret