Faits:
A. Par contrat du 20 novembre 2000, Y._ Sàrl a remis à bail à F.X._ et H.X._ des locaux commerciaux portant sur le café-restaurant A._, à ..., pour un loyer mensuel net de 8'000 fr. Les locaux loués comprennent, en sus du café-restaurant, une terrasse, des places de parc extérieures, des combles habitables, des locaux de service en sous-sol et des locaux sanitaires communs (mentionnés sous la rubrique "dépendances").
Au moment de la prise à bail, un bar-karaoké, dit B._, était exploité au sous-sol de l'immeuble. Les deux établissements partageaient les sanitaires du sous-sol, sans que cette utilisation commune ne cause de problèmes particuliers.
Du 1er août 2003 au 28 février 2006, les locaux abritant B._ et le fond de commerce ont été sous-loués par l'exploitante à un tiers et un café-bar a été ouvert sous l'enseigne C._. Dans cet établissement, ouvert de 16 heures à 1 heure du matin en semaine et jusqu'à 2 heures du matin le week-end, des femmes proposaient des services à caractère sexuel à des clients contre rémunération. Elles pouvaient être vues dans les couloirs et les toilettes communes du sous-sol, qui présentaient un aspect repoussant pour n'importe quel client du restaurant. Il n'a pas été établi que les prostituées se livraient à des actes sexuels dans les locaux du bar C._ ou dans les toilettes du sous-sol. Du fait de l'activité exercée par les prostituées, A._ a subi une atteinte à sa réputation, les clients préférant éviter le restaurant le soir pour des motifs de promiscuité gênante. S'en est suivie une baisse du chiffre d'affaires du soir, qui s'est répercutée sur le résultat du service de midi.
Par lettre du 9 septembre 2004, l'existence d'un défaut lié à la présence de prostituées dans les sous-sols de l'immeuble, en particulier dans les locaux communs du café-restaurant et du bar C._, a été portée à la connaissance de la bailleresse. Le défaut invoqué a pris fin à la date de cessation de l'exploitation du bar, le 28 février 2006.
B. Le 22 mars 2006, F.X._ et H.X._ ont ouvert action contre Y._ Sàrl devant le Tribunal des baux du canton de Vaud. Les locataires requéraient, entre autres conclusions, une réduction du prix du loyer de 50%, le loyer devant être fixé à 4'000 fr. par mois dès et y compris le 1er janvier 2004. Outre les nuisances liées à l'exploitation du bar C._, les locataires invoquaient d'autres défauts de la chose louée, comme l'éclairage insuffisant du parking extérieur.
Le 1er novembre 2006, les parties ont conclu une transaction partielle au sujet d'une partie des loyers consignés (18'000 fr.) et des loyers à consigner.
Par jugement du 5 novembre 2008, le Tribunal des baux a prononcé une réduction de loyer de 5% du 10 septembre 2004 au 28 février 2006, la bailleresse étant débitrice des locataires, solidairement entre eux, des loyers versés en trop pour cette période, à savoir 7'080 fr. Les loyers consignés ont été déconsignés en faveur des locataires à concurrence dudit montant et en faveur de la bailleresse pour le solde. Toutes autres ou plus amples conclusions ont été rejetées.
Saisie par les locataires qui réclamaient une réduction de loyer de 40% du 10 septembre 2004 au 28 février 2006, la Chambre des recours du Tribunal cantonal vaudois a statué le 21 avril 2010. Elle a partiellement admis le recours et réformé les chiffres I et II du dispositif du jugement entrepris, en ce sens que le loyer mensuel net des locaux loués a été réduit de 15% en raison des nuisances liées à l'exploitation du bar C._, la bailleresse étant la débitrice des locataires, solidairement entre eux, d'un montant de 21'240 fr. Le jugement a été confirmé pour le surplus.
En substance, la cour cantonale a estimé qu'un pourcentage de réduction de 15% était adéquat, après avoir considéré les nuisances du soir, la perte de clientèle, mais également le fait que les combles habitables, également objet du bail, n'étaient pas touchés par le défaut constaté. Elle a par ailleurs précisé que la situation d'espèce n'était pas aussi extrême que dans le précédent zurichois cité par les recourants. Tout défaut lié à l'éclairage du parking extérieur a été nié.
C. Les locataires exercent un recours en matière civile au Tribunal fédéral contre l'arrêt cantonal. Invoquant une violation des art. 256 al. 1 et 259d CO, ils concluent à l'admission du recours et à la réforme du jugement entrepris en ce sens qu'une réduction de loyer de 40% leur soit accordée, la partie adverse devant être reconnue débitrice à leur égard d'un montant de 56'640 fr., à compenser avec le montant des loyers de l'année 2005. Les locataires concluent également à la déconsignation des loyers consignés sous compte no ... et à l'octroi de dépens de seconde instance.
La bailleresse conclut, sous suite de frais et dépens, au rejet du recours.

Considérant en droit:
1. 1.1 Devant l'autorité précédente, les conclusions encore litigieuses (cf. art. 51 al. 1 let. a LTF) portaient sur une réduction supplémentaire du loyer de 35 % du 10 septembre 2004 au 28 février 2006. La recevabilité du recours en matière civile suppose notamment une valeur litigieuse minimale de 15'000 fr. dans les affaires relevant du droit du bail à loyer (art. 74 al. 1 let. a LTF). Ce seuil est largement atteint en l'espèce de sorte que le recours est recevable ratione valoris.
Pour le surplus, le recours est dirigé contre un jugement final (art. 90 LTF), rendu en matière civile (art. 72 al. 1 LTF) et en dernière instance cantonale (art. 75 al. 1 LTF). Il est formé par les locataires qui ont pris part à l'instance précédente et succombé partiellement dans leurs conclusions (art. 76 al. 1 LTF). Introduit en temps utile (art. 46 al. 1 let. b, 48 al. 1 et 100 al. 1 LTF) et dans les formes requises (art. 42 al. 1 à 3 LTF), le recours est en principe recevable.
1.2 Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.4 p. 400). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (art. 108 al. 1 let. b LTF), le Tribunal fédéral n'examine en principe que les griefs invoqués; il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 1.4 p. 400; <ref-ruling> consid. 2.2.1 p. 389). Par exception à la règle selon laquelle il examine le droit d'office, il ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (art. 106 al. 2 LTF).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (<ref-ruling> consid. 1.5 p. 130, 397 consid. 1.5 p. 401; <ref-ruling> consid. 8.1 p. 153) - ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF). Il incombe à la partie recourante, qui entend s'écarter des constatations de l'autorité précédente, d'expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'art. 105 al. 2 LTF seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (<ref-ruling> consid. 1.2 p. 187; <ref-ruling> consid. 1.4 p. 287 s. et consid. 6.2 p. 288).
Aucun fait nouveau, ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF).
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (art. 107 al. 1 LTF). Toute conclusion nouvelle est irrecevable (art. 99 al. 2 LTF).
2. La chose est défectueuse lorsqu'elle ne présente pas une qualité que le bailleur a promise ou une qualité sur laquelle le locataire pouvait légitimement compter en considération de son droit de recevoir la chose dans un état approprié à l'usage convenu, droit consacré par l'art. 256 al. 1 CO (<ref-ruling> consid. 3.2 p. 347).
En l'occurrence, le principe d'un défaut de la chose louée dû à la coexistence de clientèles différentes, à l'utilisation commune des toilettes et à la "présence de prostituées s'exhibant en tenues légères devant les toilettes au sous-sol en vue de racoler des clients" (cf. jugement entrepris, consid. 3c, p. 11) n'est pas discuté devant le Tribunal fédéral, comme il ne l'a pas été non plus devant l'instance de recours cantonale. Seule la quotité de la réduction de loyer accordée par les juges cantonaux est remise en cause par les locataires. Sur ce dernier point, les recourants soutiennent que la cour cantonale aurait dû réduire le loyer de 35%, et non pas seulement de 15%, compte tenu de l'importance du défaut constaté, qu'ils qualifient de grave.
Les recourants critiquent par ailleurs l'appréciation faite par les juges cantonaux du défaut invoqué en lien avec l'insuffisance de l'éclairage du parking extérieur et prétendent de ce chef à une réduction de loyer de 5%. La réduction globale demandée ascende ainsi à 40%.
2.1 La réduction de loyer que le locataire peut exiger en application de l'art. 259d CO doit être proportionnelle au défaut et se détermine par rapport à la valeur de l'objet sans défaut. Elle vise à rétablir l'équilibre des prestations entre les parties (<ref-ruling> consid. 4.1 p. 507; <ref-ruling> consid. 11c p. 394). En principe, il convient de procéder selon la méthode dite relative ou proportionnelle, telle qu'elle est pratiquée dans le contrat de vente: la valeur objective de la chose avec défaut est comparée à sa valeur objective sans défaut, le loyer étant ensuite réduit dans la même proportion. Cependant, le calcul proportionnel n'est pas toujours aisé, notamment lorsque le défaut est de moyenne importance. Il est alors admis qu'une appréciation en équité, par référence à l'expérience générale de la vie, au bon sens et à la casuistique, n'est pas contraire au droit fédéral (<ref-ruling> consid. 4.1 p. 507 s.).
Lorsque le juge est amené à évaluer en équité la diminution de jouissance de la chose louée, il doit apprécier objectivement la mesure dans laquelle l'usage convenu se trouve limité, en tenant compte des particularités de chaque espèce, au nombre desquelles la destination des locaux joue un rôle important (arrêt 4C.219/2005 du 24 octobre 2005 consid. 2.4 et les références citées).
Chaque fois qu'une autorité cantonale procède en équité (art. 4 CC), le Tribunal fédéral ne substitue pas sa propre appréciation à celle de l'instance inférieure; il n'intervient que si celle-ci a abusé de son pouvoir d'appréciation, c'est-à-dire si elle a retenu des critères inappropriés, si la décision rendue aboutit à un résultat manifestement injuste ou à une iniquité choquante (<ref-ruling> consid. 4.1 p. 508 et les arrêts cités).
2.2 Il convient tout d'abord d'observer que l'autorité cantonale a, avant de calculer la réduction du loyer, indiqué que le défaut était de moyenne importance - ce qui a légitimé la réduction de loyer (arrêt 4C.97/2003 du 28 octobre 2003, consid. 3.3) -, tout en précisant que cette qualification n'était contestée par aucune des parties au litige. La cour cantonale n'a donc pas omis de qualifier les défauts invoqués, contrairement à ce que prétendent les locataires devant le Tribunal fédéral (cf. recours p. 10).
Les magistrats vaudois ont estimé comme adéquate une réduction de loyer de 15%. Ils ont pris en compte l'atteinte à la réputation de l'établissement, consécutivement à la présence de prostituées dans les sous-sols de l'immeuble et les toilettes communes du bar et du restaurant, à l'état repoussant de ces dernières et à l'appréciation générale liée à la qualité de l'établissement. Ils se sont également référés à la baisse du chiffre d'affaires du soir et du midi, considérant - contrairement aux premiers juges - que la perte de clientèle du soir s'était répercutée sur le service de midi. Les juges cantonaux ont évoqué le cas zurichois relatif à une réduction de loyer de 35% octroyée à la suite de l'établissement d'un salon de massage dans un immeuble d'habitation, qui provoquait toute sorte d'inconvénients propres à diminuer dans une mesure importante l'usage de l'appartement loué, à savoir des bruits et cris provoqués par les masseuses, la présence de revues pornographiques traînant dans l'escalier, des coups de sonnette et le racolage de clients, de manière quotidienne, souvent jusqu'au petit matin, y compris le week-end. Ils ont néanmoins considéré que la situation d'espèce n'était pas aussi extrême et qu'elle ne justifiait dès lors pas une réduction aussi élevée. Ils ont de surcroît souligné que le bail portait également sur les combles habitables, lesquels n'étaient pas touchés par le défaut constaté.
Dans le cas d'espèce, tout comme dans l'affaire tranchée par les juges zurichois (publiée in Mietrechtspraxis [mp] 1988 p. 112 ss), la réduction du loyer se trouve être en corrélation avec l'exploitation, dans l'immeuble où se trouvent les objets loués, d'un commerce lié à la prostitution. Il ressort en effet des constatations cantonales que des femmes proposaient des services à caractère sexuel à des clients contre rémunération dans le café-bar C._, situé au sous-sol de l'immeuble abritant le restaurant exploité par les recourants.
Si la diminution de loyer de 15% retenue par les juges cantonaux peut paraître relativement faible, il ne faut pas perdre de vue qu'il s'agit là d'une question d'appréciation que le Tribunal fédéral ne revoit qu'avec réserve. Or, au regard des éléments retenus par l'autorité cantonale, on ne voit pas que le résultat auquel aboutit cette autorité soit inéquitable et que la réduction prononcée soit hors de proportion avec le défaut constaté.
Il convient en particulier de garder à l'esprit que seule une partie des locaux loués était touchée par le défaut dénoncé et que les locaux concernés étaient consacrés à une activité commerciale. S'il a été dûment constaté (art. 105 al. 1 LTF) que la réputation du restaurant avait été entachée et que l'établissement avait subi une baisse de fréquentation, tant le soir que lors du service de midi, en raison de la peur de l'amalgame ressentie par les clients, on notera néanmoins qu'il ne ressort pas du jugement entrepris, ni même des actes de la cause, que les parties étaient convenues de la réalisation d'un certain chiffre d'affaires et encore moins que celui réalisé était en-deçà de celui convenu; les recourants n'ont d'ailleurs fait valoir aucune créance en dommages-intérêts (art. 259e CO) du fait de la baisse du chiffre d'affaires. On rappellera d'ailleurs que le bar n'ouvrait qu'à 16 heures et fermait à 1 heure du matin en semaine et à 2 heures du matin le week-end; ce n'est donc que vers la fin de l'après-midi que les toilettes pouvaient être occupées par les prostituées, être laissées dans un état repoussant et ainsi donner une image appréciative négative du restaurant.
A en croire les recourants, le défaut serait plus important en l'espèce que dans le précédent zurichois, compte tenu de la présence des "filles" dans les espaces communs. C'est toutefois oublier que tel était également le cas à Zurich, puisque dans cette affaire une activité de racolage avait lieu dans les escaliers et l'ascenseur de l'immeuble. L'argument s'y rapportant tombe donc à faux. Les recourants s'éloignent enfin de l'état de fait déterminant lorsqu'ils prétendent que les prostituées s'adonnaient à des actes sexuels dans les toilettes communes, puisqu'il a été retenu - sans que l'arbitraire ne soit invoqué à ce sujet - que de tels actes n'avaient lieu qu'à l'extérieur de l'immeuble.
Si l'on tient compte de l'ensemble des circonstances d'espèce, il ne peut être reproché à l'autorité cantonale d'avoir abusé de son pouvoir d'appréciation en admettant un taux de réduction de 15%.
2.3 Les juges cantonaux ont rejeté les prétentions en réduction de loyer invoquées en rapport avec l'éclairage du parking extérieur. Les magistrats ont motivé leur refus par le fait qu'aucune revendication n'avait été formulée par les locataires au sujet de la faiblesse de l'éclairage du parking lors de la prise à bail en 2000, alors qu'elle existait déjà, que le contrat ne contenait aucune précision en la matière et enfin qu'aucun délai convenable n'avait été fixé à la bailleresse pour augmenter l'intensité dudit éclairage.
Il est de jurisprudence que l'on peut exiger du locataire qui exerce les droits découlant de la garantie des défauts qu'il se comporte conformément aux règles de la bonne foi (<ref-ruling> consid. 5.2 p. 509). En particulier, il doit signaler le défaut sans retard pour permettre au bailleur de prendre les mesures nécessaires afin de réduire son dommage (BERNARD CORBOZ, Les défauts de la chose louée, SJ 1979, p. 134). Le locataire qui adopte un comportement passif qui peut être interprété comme une renonciation tacite à invoquer le défaut contrevient à l'art. 2 al. 2 CC en intentant l'action découlant de l'art. 259d CO (<ref-ruling> consid. 5.2 p. 509 s.; arrêt 4A_656/2009 du 21 janvier 2010 consid. 2.2.2 et les références citées).
Les recourants ne contestent pas qu'aucun délai n'a été imparti à la bailleresse pour réparer le défaut allégué. Cela étant, la critique est vaine, sans qu'il ne soit nécessaire de l'examiner plus avant.
2.4 Au regard de ce qui précède, on ne décèle aucune violation du droit fédéral. Le recours doit en conséquence être rejeté.
3. Les frais judiciaires et les dépens sont mis à la charge de la partie qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge des recourants, solidairement entre eux.
3. Les recourants, solidairement entre eux, verseront à l'intimée une indemnité de 2'500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux parties et à la Chambre des recours du Tribunal cantonal du canton de Vaud.
Lausanne, le 25 janvier 2011
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Klett Crittin