Faits:
A. A.a L'immeuble sis rue A._ et rue B._ à C._ est constitué en propriété par étages depuis 1985.
X._ et Y._ sont copropriétaires pour moitié chacun de l'unité d'étage no 2620-68, située au rez-de-chaussée de cet immeuble, part de copropriété qu'ils ont respectivement acquise le 4 septembre 2000 et le 9 juin 2005.
D'après le registre foncier, le rez-de-chaussée de l'immeuble est destiné à l'activité commerciale et les étages à l'habitation.
A.b Depuis 1998, la "Communauté des copropriétaires d'étages de l'immeuble sis rue A._," (ci-après CCE) est régie par le règlement d'administration et d'utilisation de la copropriété (ci-après RAUC) "type", édition 1997, élaboré par le Groupement des propriétaires d'appartement de la Chambre genevoise immobilière et la Société des régisseurs de Genève. Ce règlement et les modifications qui y ont été apportées sont mentionnés au registre foncier.
Jusqu'au 12 avril 2010, le RAUC prévoyait notamment:
Art. 10 - Destination des locaux
Les parties privées et les parties communes ne peuvent servir qu'à l'usage auquel elles sont destinées (al. 1). Les changements d'affectation des parties privées doivent être autorisés par une décision de l'Assemblée des copropriétaires prise à la double majorité définie à l'article 37 du règlement (al. 2). Les changements d'affectation des parties communes doivent être autorisés par une décision de l'Assemblée générale prise à l'unanimité (al. 3).
Art. 37 - Décisions prises à la majorité double
Lorsqu'une double majorité est exigée par la loi ou les dispositions du présent règlement, les décisions ne peuvent être prises que si les copropriétaires formant la majorité des voix exprimées telle que prévue à l'article 35 al. 2, possèdent en outre, leurs parts réunies, plus de la moitié de la chose (al. 1).
A.c Le rez-de-chaussée de l'immeuble est actuellement occupé par une agence de location de voitures, un pressing, un magasin d'électroménager ainsi qu'un bar à café; la licéité de l'exploitation de ce dernier commerce au sein de l'unité d'étage appartenant à X._ et à Y._ fait l'objet du présent litige.
Un "faux trottoir", ou terrasse, partie commune de l'immeuble, longe les vitrines de ces différentes arcades.
Jusqu'en 2007, l'arcade commerciale constituée sous l'unité d'étage de X._ et de Y._ a été louée à divers commerçants, lesquels y ont successivement exploité un magasin de chaussures, un magasin d'accessoires et une librairie-agence de voyage. Le "faux trottoir" était alors utilisé pour exposer une partie des marchandises à vendre.
A.d Au début de l'année 2008, les susnommés ont entrepris d'importants travaux dans l'arcade en vue de l'ouverture d'un café-bar.
Dès août 2008, D._ en a débuté l'exploitation, sous l'enseigne E._ Bar Café. L'attention du nouveau locataire, au bénéfice d'un contrat de bail d'une durée de dix ans, a été attirée sur le fait qu'un changement d'affectation de l'arcade par rapport à l'agence de voyage qui y était exploitée auparavant nécessitait diverses autorisations, notamment celle de la CCE. Celle-ci n'a pas été requise.
D._ a également installé trois tables et neuf chaises sur le "faux trottoir" longeant la vitrine de l'arcade, constituant ainsi une terrasse pour le café-bar. L'établissement, ouvert du lundi au samedi de 7h00 à 02h00 et le dimanche de 08h00 à 02h00, propose des boissons et une petite restauration chaude (sandwiches et paninis).
A.e Dès le début des travaux précités, la CCE ainsi que divers copropriétaires ont manifesté leur désaccord au projet de X._ et Y._, en vain. Ils ont notamment requis la cessation des travaux, contraires, selon eux, au RAUC et à la volonté de la majorité des copropriétaires, lesquels avaient déjà eu l'occasion de s'exprimer contre le changement d'affectation des lots, quel qu'il soit, au cours de diverses assemblées générales, notamment les 18 septembre 2001 et 20 décembre 2006.
Le 19 juin 2008, l'assemblée générale a attiré l'attention de X._ sur le fait qu'il allait lui être prochainement demandé de remettre dans son état d'origine l'arcade dont elle était copropriétaire.
B.a B.a.a Le 27 août 2008, la CCE a assigné X._ et Y._ devant le Tribunal de première instance du canton de Genève, concluant à ce qu'il soit notamment ordonné aux intéressés de "remettre en état" leur arcade commerciale dans un délai de 30 jours, ainsi que d'enlever la terrasse installée sur les parties communes dans un délai de 15 jours, le tout sous la menace des peines prévues à l'<ref-law>.
B.a.b En cours de procédure, le 12 avril 2010, une modification du RAUC, notamment de ses art. 10 et 37, a été approuvée par l'assemblée générale à la double majorité. Cette modification impliquait en substance: 1) l'exigence d'un vote à la double majorité préalablement à tout changement d'affectation commerciale des arcades du rez-de-chaussée; 2) l'interdiction de principe, sans possibilité de recours à une approbation de l'assemblée des copropriétaires, de certaines activités commerciales jugées nuisibles, telles que café, bar, restaurant et activités liées au commerce du sexe (art. 10 let. e RAUC); 3) l'interdiction de principe, sans possibilité de recours à une approbation de l'assemblée, de tout changement de destination d'un local-dépôt en sous-sol.
X._ et Y._, qui ont voté contre les modifications adoptées, ont saisi le Tribunal de première instance d'une action en annulation de la décision du 12 avril 2010. L'instruction de la procédure a été suspendue jusqu'à droit jugé dans la présente cause.
B.b Par jugement du 23 septembre 2010, le Tribunal de première instance a ordonné à X._ et Y._ de cesser, dans le délai d'un mois dès l'entrée en force du jugement, d'affecter leur arcade à l'exploitation d'un café-bar (ch. 1), dit que cette injonction était prononcée sous la menace de la peine prévue à l'<ref-law> (ch. 2), condamné les intéressés aux frais et dépens (ch. 3 et 4) et débouté les parties de toutes autres conclusions (ch. 5).
Statuant le 26 août 2011 sur appel de X._ et Y._, la Cour de justice a confirmé le jugement attaqué et débouté les parties de toutes autres conclusions. L'arrêt a été notifié aux parties le 1er septembre 2011.
C. Par acte du 30 septembre 2011, X._ et Y._ (ci-après les recourants) déposent un recours en matière civile et un recours constitutionnel subsidiaire devant le Tribunal fédéral. Ils concluent principalement à l'annulation de l'arrêt cantonal et à sa réforme en ce sens que la CCE (ci-après l'intimée) est déboutée de l'intégralité des conclusions prises aux termes de sa demande du 27 août 2008; subsidiairement, ils réclament le renvoi de la cause à l'autorité cantonale pour nouvelle décision. A l'appui de leurs conclusions, les recourants invoquent une atteinte injustifiée à leur garantie de la propriété et à leur liberté économique (art. 26 et 27 Cst.) ainsi que l'application arbitraire des <ref-law> et 8 CC; ils se plaignent également d'un déni de justice formel et matériel (art. 29 Cst.).
Invitées à se déterminer, la cour cantonale s'est référée aux considérants de son arrêt, tandis que l'intimée a conclu à ce que les recourants soient déboutés de leur recours.
D. La requête d'effet suspensif formée par les recourants a été admise par ordonnance présidentielle du 19 octobre 2011.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 3, 462 consid. 2, p. 465).
1.1 L'arrêt entrepris a été rendu dans une affaire civile (<ref-law>), de nature pécuniaire.
1.1.1 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). Ce contrôle d'office ne supplée toutefois pas au défaut d'indication de la valeur litigieuse: il n'appartient pas en effet 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 (<ref-ruling> consid. 1.1.1 et les références). Le recourant doit ainsi donner, 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.1).
1.1.2 La Cour de justice n'a pas arrêté la valeur litigieuse, se contentant d'observer qu'elle était indéterminée, mais à tout le moins supérieure à 8'000 fr. Les recourants affirment qu'elle serait supérieure à 30'000 fr. Ils soutiennent à cet égard que, dans l'hypothèse où leur recours serait rejeté, ils seraient contraints de mettre un terme prématuré au contrat de bail conclu avec l'exploitant du café-bar, démarche qui serait inévitablement accompagnée de pertes de loyers; les équipements spécifiques à l'exploitation d'un café-bar devraient en outre être démontés et l'interdiction en cause restreindrait les possibilités de relocation ultérieure. Les recourants remarquent enfin que la procédure aurait généré d'importants frais judiciaires, qu'ils chiffrent actuellement à 20'000 fr.
Ce dernier argument n'est manifestement pas pertinent pour chiffrer la valeur litigieuse. Quant aux autres éléments également invoqués, s'il est évident qu'ils ont des impacts économiques, les recourants ne prennent toutefois pas la peine de les chiffrer. Il s'ensuit qu'il est donc impossible de constater d'emblée et avec certitude que leur addition atteint bien la somme de 30'000 fr. (<ref-law>). Faute de constatations ou d'éléments d'appréciation permettant au Tribunal fédéral de fixer aisément la valeur litigieuse, le recours en matière civile est donc irrecevable au regard de l'<ref-law>.
1.2 Dans la mesure où les recourants ne prétendent pas que leur recours soulèverait une question juridique de principe (<ref-law>), il reste à déterminer s'il est recevable au titre de recours constitutionnel subsidiaire (<ref-law>).
Dirigé contre une décision finale (<ref-law> applicable par renvoi de l'<ref-law>), rendue par un tribunal supérieur statuant sur recours en dernière instance cantonale (<ref-law> applicable par renvoi de l'<ref-law>), le recours est en principe recevable. Il a également été déposé en temps utile (<ref-law> applicable par renvoi de l'<ref-law>), par les parties qui ont pris part à la procédure devant l'autorité précédente et démontrent un intérêt juridique à la modification de l'arrêt attaqué (<ref-law>).
1.3 Contrairement à ce qu'affirment les recourants, ils n'ont pas déposé deux recours dans un seul mémoire comme le leur permet l'<ref-law>. Ils n'ont au contraire formé qu'un seul recours, intitulé à la fois recours en matière civile et recours constitutionnel subsidiaire. Il résulte du considérant qui précède qu'en tant que recours en matière civile, le recours est irrecevable. A lui seul, l'intitulé erroné d'un recours ne nuit cependant pas à son auteur, pour autant que les conditions d'une conversion en la voie de droit adéquate soient réunies (<ref-ruling> consid. 1.2 p. 382 et les arrêts cités). C'est le cas en l'espèce, de sorte qu'il convient de traiter l'écriture comme un recours constitutionnel subsidiaire. Seule peut en conséquence être invoquée la violation des droits constitutionnels (<ref-law>).
2. La Cour cantonale a laissé indécise la question de savoir si l'exploitation d'un café-bar au sein de la part d'étages des appelants était ou non conforme aux dispositions du règlement de la PPE dans sa teneur antérieure au 12 avril 2010, date de l'adoption par l'intimée des nouvelles dispositions réglementaires. La juridiction a en effet considéré que la modification réglementaire votée à cette dernière date prévoyait expressément que les activités commerciales telles que café et bar étaient désormais interdites au sein d'une arcade commerciale (art. 10 let. e RAUC). Cette décision ne contenait aucune réserve en faveur des établissements d'ores et déjà exploités, de sorte qu'elle déployait un effet obligatoire pour tous les propriétaires d'étages. En l'absence d'indices contraires recueillis dans le cadre de la présente procédure, il ne pouvait être retenu que l'interdiction votée le 12 avril 2010 devrait être considérée comme absolument nulle, faute pour celle-ci de consacrer a priori une violation des règles de forme importantes ou d'aller à l'encontre de la structure fondamentale de la propriété par étages. Il s'ensuivait que, dans la mesure où les recourants n'avaient pas sollicité de mesures provisionnelles dans le cadre de la procédure en annulation de la décision du 12 avril 2010, l'interdiction d'exploitation votée déployait actuellement ses effets, le juge saisi de l'action en annulation dans le cadre de la procédure parallèle ne s'étant pas encore prononcé sur la validité de cette décision.
3. 3.1 Les recourants reprochent à la cour cantonale d'avoir interprété le nouvel art. 10 let. e RAUC de manière insoutenable et ce, sans qu'aucun allégué des parties ne l'y invitât. La Cour de justice ne pouvait en effet déduire qu'en l'absence de réserve en faveur des établissements d'ores et déjà exploités avant le vote du 12 avril 2010, les nouvelles dispositions s'appliqueraient également ipso jure à ces derniers. L'absence de précision à cet égard dans les articles nouvellement adoptés ne permettait pas en effet de leur imposer un effet rétroactif, les recourants soulignant au demeurant qu'ils s'étaient prévalu de la nullité desdites dispositions dans le cadre de la procédure en annulation de la décision les adoptant.
L'intimée soutient à ce propos que les recourants n'avaient pas requis de mesures provisionnelles à l'appui de leur action en annulation de la décision prise le 12 avril 2010, de sorte que la nouvelle réglementation leur était actuellement applicable. De surcroît, l'application de l'effet rétroactif n'aurait aucune conséquence juridique dès lors qu'il s'agissait uniquement de cesser une activité commerciale qui n'avait jamais été approuvée par l'assemblée générale et qui était contestée depuis le début des travaux en 2008.
3.2 L'<ref-law> pose le principe général de la non-rétroactivité des lois: les effets juridiques de faits antérieurs à l'entrée en vigueur du code civil continuent ainsi à être régis par les dispositions du droit sous l'empire duquel ces faits se sont produits (al. 1), principe que l'alinéa 2 répète en ce qui concerne les effets juridiques des actes accomplis avant l'entrée en vigueur du nouveau droit, tandis que les faits postérieurs à l'entrée en vigueur du nouveau droit sont régis par celui-ci (al. 3; <ref-ruling> consid. 2.1.1 et la référence citée). Le rattachement d'un rapport d'obligation au droit en vigueur au moment de sa constitution, tel que le prévoit l'<ref-law>, vise à protéger la confiance subjective des parties, qui ont soumis leurs relations à un droit matériel qui leur était connu, et tend aussi à empêcher que des droits valablement acquis par un acte juridique soient enlevés à leur titulaire par le seul effet de la loi (<ref-ruling> consid. 2.1.1 et la référence).
En dérogation au principe général de non-rétroactivité posé par l'<ref-law>, l'<ref-law> prévoit que les règles établies dans l'intérêt de l'ordre public et des moeurs sont applicables, dès leur entrée en vigueur, à tous les faits pour lesquels la loi n'a pas prévu d'exception (al. 1); en conséquence, les dispositions de l'ancien droit, qui, d'après le droit nouveau, sont contraires à l'ordre public ou aux moeurs, ne peuvent plus recevoir d'application (al. 2; <ref-ruling> consid. 2.1.2 et les références).
Ces différents principes ont une portée générale (<ref-ruling> consid. 3a; cf. PAUL-HENRI STEINAUER, Le titre préliminaire du Code civil in: Traité de droit privé suisse, tome II/1, 2009, n. 115) et trouvent systématiquement application dans le domaine du droit privé lorsque les dispositions de droit transitoire font défaut ou manquent de clarté (<ref-ruling> consid. 4; <ref-ruling> consid. 3c; MARKUS VISCHER, in Basler Kommentar, ZGB II, 3e éd. 2007, n. 2 ad <ref-law>).
3.3 A supposer qu'en cours de procédure, l'intimée eût allégué l'effet rétroactif du nouveau règlement, les principes sus-exposés ne permettaient pas à la Cour de justice de déduire, sans faire preuve d'arbitraire, de l'absence de réserve liée au droit transitoire l'application immédiate dudit règlement à des situations existantes et exécutées en conformité de l'ancienne réglementation.
La cause doit par conséquent lui être renvoyée afin qu'elle détermine si, conformément au règlement en vigueur au début 2008, l'exploitation de l'arcade commerciale en café-bar constituait un changement d'affectation soumis à l'approbation de l'assemblée des copropriétaires prise à la double majorité (art. 10 al. 2 de l'ancien règlement). Dans la négative, elle devra encore se prononcer sur la conclusion relative à l'enlèvement de la terrasse installée sur le faux trottoir (partie commune), question qui n'a pas été examinée par les instances cantonales successives, le Tribunal de première instance ayant jugé que l'exploitation de l'arcade en café-bar contrevenait au règlement antérieur à 2010 et la Cour de justice au nouveau règlement.
4. Le sort du litige étant scellé par le considérant précédent, les autres griefs soulevés par les recourants deviennent ainsi sans objet.
5. En définitive, le recours en matière civile est irrecevable tandis que le recours constitutionnel subsidiaire doit être admis, l'arrêt cantonal annulé et la cause renvoyée à la Cour de justice pour nouvelle décision au sens des considérants. Les frais judiciaires sont mis à la charge de l'intimée qui succombe (<ref-law>); celle-ci versera en outre une indemnité de dépens aux recourants (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours en matière civile est irrecevable.
2. Le recours constitutionnel subsidiaire est admis, l'arrêt attaqué annulé et la cause renvoyée à la cour cantonale pour nouvelle décision au sens des considérants.
3. Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge de l'intimée.
4. Une indemnité de 3'000 fr., à payer aux recourants à titre de dépens, est mise à la charge de l'intimée.
5. Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre civile.
Lausanne, le 10 janvier 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