Faits:
A. A.a Le 1er février 2001, les époux A._ ont acquis en copropriété la parcelle no 57 de la Commune de C._, sur laquelle est érigé le bâtiment ECA no 62.
B._ est propriétaire de la parcelle no 58, située dans la même commune, sur laquelle se trouve le bâtiment ECA no 255.
A.b Le plan cadastral, numérisé en 1998, indique que le mur séparant les parcelles nos 57 et 58 est mitoyen sur toute sa longueur. Les époux A._ se sont fondés sur ce plan en acquérant leur bien-fonds.
En 2002, le Département des finances et des relations extérieures du canton de Vaud a reconnu qu'il existait toutefois une divergence entre le plan numérisé et le plan original, en ce sens que, selon ce dernier, levé entre 1905 et 1906, le mur susmentionné était mitoyen sur une partie de sa longueur seulement, à savoir sur le premier segment situé à l'est des bâtiments, le reste du mur se situant exclusivement sur la parcelle no 58, propriété de B._. Selon les indications du géomètre E._, la ligne séparant les immeubles ne passe ainsi pas par le milieu du mur.
Prenant acte de l'erreur survenue lors de la numérisation cadastrale, le registre foncier du district de Lavaux a procédé d'office - sans en informer les parties - à la correction du plan numérisé afin de le rendre conforme au plan initial, de sorte que le mur apparaît désormais comme étant partiellement mitoyen.
B. Par demande du 23 avril 2009 déposée devant le Président du Tribunal d'arrondissement de l'Est vaudois, les époux A._ ont ouvert action contre B._, concluant à la rectification du registre foncier du district de Lavaux "en ce sens que le plan représentant le mur délimitant le bâtiment no ECA 62 de la parcelle no 57 de la Commune de C._ du bâtiment ECA no 255 de la parcelle no 58 de la Commune de C._ est représenté comme mitoyen sur toute sa longueur" (sic), le conservateur du registre foncier étant invité à procéder à cette rectification.
Les demandeurs ont obtenu gain de cause en première instance.
Statuant sur recours de B._, la Chambre des recours du tribunal cantonal vaudois l'a admis (ch. I) et réformé le jugement attaqué en ce sens que la demande de rectification du registre foncier est rejetée (ch. 2). L'arrêt, rendu le 16 février 2011, a été notifié aux parties le 25 mai 2011.
C. Le 27 juin 2011, les époux A._ (ci-après les recourants) interjettent un recours en matière civile devant le Tribunal fédéral, concluant à la réforme de l'arrêt qu'ils attaquent en ce sens que le recours formé par B._ (ci-après l'intimé) est rejeté et le ch. 2 du dispositif supprimé. Les recourants invoquent la violation de leur droit d'être entendu, de même que celle des art. 3 al. 1 et 973 al. 1 CC.
Des déterminations n'ont pas été demandées.
D. Par ordonnance du 15 juillet 2011, la Présidente de la cour de céans a admis la requête de mesures provisionnelles déposée par les recourants, de sorte que l'inscription provisoire au registre foncier du litige les opposant à l'intimé a été maintenue.

Considérant en droit:
1. 1.1 La décision entreprise est une décision finale (<ref-law>), rendue en matière civile (<ref-law>), par le tribunal supérieur du canton de Vaud, statuant en dernière instance et sur recours (<ref-law>); le recours est interjeté par la partie qui a succombé dans ses conclusions devant l'instance précédente (<ref-law>), dans le délai prévu par la loi (<ref-law>).
1.2 Le recours en matière civile n'est ouvert que si la valeur litigieuse minimale fixée par la loi, en l'espèce 30'000 fr., est atteinte (<ref-law>). C'est le montant litigieux devant la dernière instance cantonale qui est déterminant (<ref-law>) et celle-ci doit le mentionner dans son arrêt (art. 112 al. 1 let. d LTF). Lorsque les conclusions ne tendent pas au paiement d'une somme d'argent déterminée, le Tribunal fédéral fixe la valeur litigieuse selon son appréciation (<ref-law>), comme sous l'ancien droit (art. 36 al. 2 OJ; cf. Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, in FF 2001, ch. 4.1.2.6 in fine, p. 4099). Il n'appartient toutefois pas au Tribunal fédéral de procéder lui-même à des investigations pour déterminer cette valeur, si elle ne résulte pas d'emblée des constatations de la décision attaquée (<ref-law>) ou d'autres éléments ressortant du dossier. Le recourant doit ainsi indiquer, conformément à l'art. 42 al. 1 et 2 LTF, les éléments suffisants pour permettre au Tribunal de céans d'estimer aisément la valeur litigieuse sous peine d'irrecevabilité. Celui-ci n'est toutefois lié ni par l'estimation de la partie recourante ou un accord des parties, ni par une estimation manifestement erronée de l'autorité cantonale (<ref-ruling> consid. 1.1).
La cour cantonale n'a pas arrêté la valeur litigieuse, mais s'est limitée à indiquer que le seuil de 30'000 fr. n'était pas atteint. Les recourants soutiennent le contraire. Ils observent en effet, en se fondant sur une expertise commandée par leurs soins et établie le 18 juin 2011 par un bureau d'ingénieurs, que, si le mur litigieux ne devait pas être considéré comme mitoyen, ils perdraient le contrôle de l'intégrité structurelle de leur bâtiment. Ledit rapport fixe le coût des travaux destinés à supprimer cette dépendance structurelle à 65'995 fr. Ces allégations, appuyées par un expert que les recourants ont pris la peine de mandater, apparaissent fondées. Il faut ainsi admettre que la valeur litigieuse de 30'000 fr. est atteinte et que le recours en matière civile est en principe recevable.
2. Le Tribunal fédéral applique en principe le droit d'office (<ref-law>), sans être lié ni par les motifs de l'autorité précédente, ni par les moyens des parties; il peut donc admettre le recours en se fondant sur d'autres arguments que ceux invoqués par le recourant, comme il peut le rejeter en opérant une substitution de motifs (parmi plusieurs: <ref-ruling> consid. 1.1; <ref-ruling> consid. 2.2).
3. 3.1 Le Président du Tribunal d'arrondissement a fait droit aux conclusions des recourants, jugeant qu'on ne pouvait leur reprocher de ne pas avoir consulté les pièces leur permettant de constater que le plan du registre foncier - numérisé en 1998 - ne correspondait pas à l'original - levé en 1905/1906 -, celui-ci étant archivé. Ignorant la divergence et en se fondant sur les indications du registre foncier, les recourants avaient ainsi acquis de bonne foi la mitoyenneté du mur et devaient être maintenus dans leur acquisition, conformément à l'<ref-law>.
3.2 Statuant sur recours de l'intimé, la cour cantonale a en revanche rejeté la demande de rectification formulée par les recourants.
La juridiction a avant tout admis qu'il y avait eu une erreur lors de la numérisation du plan cadastral, ce qui, en soi, devait donner lieu à la rectification du registre foncier. Elle a ensuite examiné si les acquéreurs pouvaient invoquer l'<ref-law> et la protection de leur bonne foi en arguant s'être exclusivement fondés sur le plan consulté au registre foncier, à savoir le plan numérisé de 1998. A cet égard, les juges cantonaux ont observé que la présomption de mitoyenneté de l'<ref-law> pouvait être renversée par un usage local contraire. En présence d'un tel usage, l'acquéreur devait alors faire preuve d'une diligence accrue pour être de bonne foi au sens de l'<ref-law>. S'agissant des murs dont la fonction ne se limitait pas, comme en l'espèce, à séparer deux propriétés, les art. 441 s. du code civil vaudois de 1819 valaient toujours comme usage local et avaient le pas sur l'<ref-law>. Selon l'art. 442 du code civil vaudois de 1819, les ouvertures existantes dans un mur constituaient des signes de non-mitoyenneté et, par conséquent, une présomption légale de non-mitoyenneté. Or, lorsque les recourants avaient acquis leur immeuble, le mur était doté, dans son segment litigieux, d'un "jour" en brique de verre. Celui-ci constituait une ouverture au sens de l'art. 442 précité et, ainsi, une présomption de non-mitoyenneté. Les juges cantonaux en ont conclu qu'en tant que l'indication de mitoyenneté figurant sur le plan du registre foncier était contredite par une présomption de non-mitoyenneté, les recourants auraient dû se montrer particulièrement vigilants en se portant acquéreurs de leur immeuble et, en conséquence, procéder à des vérifications supplémentaires, notamment en consultant le plan original archivé. En tant qu'ils n'avaient pas établi avoir effectué cette démarche, ils n'étaient pas fondés à invoquer leur bonne foi pour être maintenus dans leur acquisition.
4. 4.1 Les recourants tendent, par leur action, à faire rétablir le plan sur lequel ils se sont fondés lors de l'acquisition de leur bien-fonds, à savoir le plan cadastral numérisé de 1998. Ils invoquent la violation des art. 3 al. 1 et 973 al. 1 CC, prétendant s'être fiés de bonne foi au dit plan, déposé alors au registre foncier.
A l'appui de cette affirmation, ils remarquent que les escaliers, le toit, ainsi qu'une arche de leur immeuble étaient ancrés dans le mur litigieux, sans que ces aménagements ne bénéficient d'une servitude, circonstance qui leur avait permis de légitimement conclure que l'absence de servitude s'expliquait par le caractère mitoyen du mur, confirmé par le plan du registre foncier. Les recourants soulignent également que la solution retenue par la cour cantonale se fondait exclusivement sur l'opinion doctrinale du Professeur Piotet, celle-ci supposant qu'ils étaient en mesure d'identifier l'existence d'une présomption de non-mitoyenneté en se fondant sur un usage local établi en l'espèce par l'art. 442 du code civil vaudois de 1819, à savoir la présence de briques de verre dans un segment du mur litigieux. Or, on ne pouvait exiger d'eux que, lors de la consultation du registre foncier, ils connaissent cet avis doctrinal que la jurisprudence fédérale n'avait au demeurant jamais confirmé. En juger autrement reviendrait à rendre inefficient le principe de la publicité et de la sécurité attaché à l'institution du registre foncier et à exiger de tout acquéreur d'immeuble qu'il dispose de connaissances juridiques très pointues en matière de droit foncier, a fortiori à être assisté d'un juriste spécialisé lors de la consultation du registre foncier. Les recourants observent en outre que l'art. 442 du code civil vaudois désignait comme marque de non-mitoyenneté les ouvertures existantes, telles que les portes et les fenêtres ou les signes de ces anciennes ouvertures, comme les tablettes, cadres et corniches. Rien ne permettait dès lors de confirmer que, s'ils avaient eu connaissance de ladite disposition, ils auraient envisagé que les briques de verre pouvaient être assimilées à des ouvertures. Enfin, à supposer que le plan original pût constituer une pièce justificative - ce dont ils doutaient -, les recourants observent qu'ils auraient pu légitimement présumé que la différence entre ce dernier plan et celui qu'ils avaient consulté pouvait s'expliquer par un changement de statut du mur, intervenu consensuellement entre les propriétaires au cours des nonante années écoulées.
A l'appui de cette affirmation, ils remarquent que les escaliers, le toit, ainsi qu'une arche de leur immeuble étaient ancrés dans le mur litigieux, sans que ces aménagements ne bénéficient d'une servitude, circonstance qui leur avait permis de légitimement conclure que l'absence de servitude s'expliquait par le caractère mitoyen du mur, confirmé par le plan du registre foncier. Les recourants soulignent également que la solution retenue par la cour cantonale se fondait exclusivement sur l'opinion doctrinale du Professeur Piotet, celle-ci supposant qu'ils étaient en mesure d'identifier l'existence d'une présomption de non-mitoyenneté en se fondant sur un usage local établi en l'espèce par l'art. 442 du code civil vaudois de 1819, à savoir la présence de briques de verre dans un segment du mur litigieux. Or, on ne pouvait exiger d'eux que, lors de la consultation du registre foncier, ils connaissent cet avis doctrinal que la jurisprudence fédérale n'avait au demeurant jamais confirmé. En juger autrement reviendrait à rendre inefficient le principe de la publicité et de la sécurité attaché à l'institution du registre foncier et à exiger de tout acquéreur d'immeuble qu'il dispose de connaissances juridiques très pointues en matière de droit foncier, a fortiori à être assisté d'un juriste spécialisé lors de la consultation du registre foncier. Les recourants observent en outre que l'art. 442 du code civil vaudois désignait comme marque de non-mitoyenneté les ouvertures existantes, telles que les portes et les fenêtres ou les signes de ces anciennes ouvertures, comme les tablettes, cadres et corniches. Rien ne permettait dès lors de confirmer que, s'ils avaient eu connaissance de ladite disposition, ils auraient envisagé que les briques de verre pouvaient être assimilées à des ouvertures. Enfin, à supposer que le plan original pût constituer une pièce justificative - ce dont ils doutaient -, les recourants observent qu'ils auraient pu légitimement présumé que la différence entre ce dernier plan et celui qu'ils avaient consulté pouvait s'expliquer par un changement de statut du mur, intervenu consensuellement entre les propriétaires au cours des nonante années écoulées.
4.2 4.2.1 Celui qui acquiert la propriété ou d'autres droits réels en se fondant de bonne foi sur une inscription du registre foncier est maintenu dans son acquisition (<ref-law>). La bonne foi, qui doit exister au moment de l'acquisition, est présumée (<ref-law>). Les inscriptions figurant au registre foncier sont en outre réputées exactes (aspect positif de la foi publique) et complètes (aspect négatif de la foi publique; <ref-ruling> consid. 3.3.1, 153 consid. 4.1.1). L'exactitude du plan, qui est partie constitutive du registre foncier (<ref-law>), est également élevée au rang de fiction à l'égard de l'acquéreur de bonne foi du fonds (<ref-law>; arrêt 5A_365/2008 du 27 octobre 2008 consid. 3.1 et les références citées).
4.2.2 La protection de la bonne foi n'est toutefois pas absolue; alors même qu'il est en réalité de bonne foi, l'acquéreur ne peut pas invoquer la protection légale qui y est attachée s'il n'a pas fait preuve de l'attention que les circonstances permettaient d'exiger de lui (<ref-law>; cf. <ref-ruling> consid. 3.3.2, 153 consid. 4.1.2; <ref-ruling> consid. 2c). Il s'ensuit que, lorsque l'acquéreur a connaissance de faits propres à faire douter de l'exactitude du registre foncier, il doit s'enquérir plus avant (<ref-ruling> consid. 3.3.2, 153 consid. 4.1.2 et la jurisprudence citée). La mesure de cette vigilance particulière constitue une question de droit, soumise au pouvoir d'appréciation du juge (<ref-law>; <ref-ruling> consid. 3.3.2, 153 consid. 4.1.2).
4.2.3 L'état physique réel et extérieurement visible d'un bien-fonds ("natürliche Publizität") peut notamment faire échec à la bonne foi du tiers acquéreur dans l'inscription figurant au registre foncier (<ref-ruling> consid. 3.3.3, 153 consid. 4.1.3). Dans ce sens, la jurisprudence a admis, à propos d'une servitude de droit de passage que, dans la mesure où, en principe, nul n'achète un immeuble au bénéfice d'une telle servitude sans visiter les lieux, le tiers acquéreur ne pourra ignorer de bonne foi - sauf dans des circonstances tout à fait spécifiques - les particularités non mentionnées dans l'inscription (assiette de la servitude, ouvrages, largeur rétrécie par endroits, etc.) qu'une telle visite pouvait lui révéler (<ref-ruling> consid. 3.3.3 et les références citées, 153 consid. 4.2.3). Il s'ensuit qu'en principe, les limitations résultant de l'état des lieux visibles sur le terrain sont opposables au tiers acquéreur, lequel ne pourra invoquer sa bonne foi s'il n'en a pas pris connaissance. Il n'est toutefois pas nécessaire qu'il en ait pris conscience dans les faits: il suffit qu'il eût pu et dû le réaliser en faisant preuve de l'attention nécessaire (<ref-ruling> consid. 4.1.3).
4.2.4 En l'espèce, il ne pouvait échapper aux recourants que le mur de leur maison et celui du bâtiment appartenant à l'intimé ne sont mitoyen qu'en partie seulement. En observant les deux maisons depuis la rue ... (ouest), l'on remarque en effet que, si leurs murs sont reliés à un seul endroit précis par une petite arche, ils ne sont en revanche nullement contigus sur l'avant: au contraire, ils sont nettement séparés l'un de l'autre par une série d'escaliers. Ils deviennent ensuite mitoyens en se rejoignant au-delà des escaliers qui les séparent. L'état physique réel et extérieurement visible du bien-fonds, dont les recourants ne prétendent pas qu'il différerait aujourd'hui de l'époque à laquelle ils se sont portés acquéreurs de leur immeuble, leur est ainsi opposable: en faisant preuve de l'attention commandée par les circonstances (contradiction entre le plan numérisé déposé au registre foncier et l'état des lieux physique), les intéressés auraient ainsi dû procéder à des investigations complémentaires, notamment en consultant le plan cadastral original.
5. Au vu de ce qui précède, il convient de déclarer sans objet les griefs des recourants relatifs à l'établissement arbitraire des faits et à la violation de leur droit d'être entendus. Ceux-ci sont en effet exclusivement liés à la motivation adoptée par la cour cantonale que la cour de céans, statuant par substitution de motifs, a finalement écartée.
6. En définitive, le recours doit être rejeté et les frais judiciaires mis à la charge des recourants qui succombent (art. 66 al. 1 et 5 LTF). L'intimé n'a droit à aucun dépens puisqu'il n'a pas été invité à se déterminer sur le fond, étant précisé qu'il s'était opposé à l'octroi de mesures provisionnelles, finalement accordées aux recourants.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge des recourants solidairement entre eux.
3. Le présent arrêt est communiqué aux parties, à la Chambre des recours du Tribunal cantonal du canton de Vaud et au Registre foncier du district de Lavaux.
Lausanne, le 2 novembre 2011
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