Sachverhalt:
A. Die Ehegatten X._ (Mieter) sind Mieter einer 3-Zimmerwohnung in Z._. Die betreffende Liegenschaft steht im Eigentum der Y._ Anlagestiftung (Vermieterin). Weil den Mietern mangels Regulierbarkeit der Heizung hohe Nebenkosten anfielen und der der Vermieterin bekannte Mangel noch nicht beseitigt war, drohten die Mieter mit Schreiben vom 17. Februar 2010 und 3. März 2010 der Vermieterin die Hinterlegung der Mietzinse bei der Staatlichen Schlichtungsstelle für Mietstreitigkeiten (SSM) an. Die Heizung wurde am 19. März 2010 repariert, worüber die Mieter gleichentags schriftlich informiert wurden. Am 27. März 2010 hinterlegten sie den Aprilmietzins ankündigungsgemäss bei der SSM, gleich wie in der Folge die Mietzinse für die Monate Mai und Juni 2010. Mit Schreiben vom 15. April 2010 setzte die Vermieterin den Mietern eine Frist von 30 Tagen zur Zahlung des ausstehenden Mietzinses unter der Androhung der Kündigung nach <ref-law>. Die Mieter hielten jedoch an der Mietzinshinterlegung fest, obwohl der Mangel gemäss ihren eigenen Angaben behoben war. Die hierauf mit Schreiben vom 27. Mai 2010 auf Ende Juni 2010 ausgesprochene Kündigung des Mietverhältnisses durch die Vermieterin zufolge Zahlungsverzugs fochten die Mieter rechtzeitig bei der SSM an, indem sie ihr dort bereits hängiges Rechtsbegehren auf Mietzinsreduktion erweiterten. Anlässlich der Schlichtungsverhandlung vom 2. Juni 2010 schlossen die Parteien einen Vergleich über die Mietzinsreduktion und die Rückzahlung zu viel bezahlter Heizkosten, nicht jedoch über die Kündigung, welche die SSM als unwirksam erklärte.
B. Am 1. Juli 2010 klagte die Vermieterin beim Zivilgericht Basel-Stadt auf Aufhebung des Entscheides der SSM vom 2. Juni 2010 und auf Feststellung, dass das Mietverhältnis zwischen den Parteien aufgrund ihrer Kündigung vom 27. Mai 2010 per 30. Juni 2010 beendet worden ist. Das Zivilgericht wies die Klage mit Urteil vom 22. November 2010 ab und stellte die Unwirksamkeit der Kündigung vom 27. Mai 2010 fest. Das Appellationsgericht des Kantons Basel-Stadt hob jedoch dieses Urteil in Gutheissung einer Beschwerde der Vermieterin am 29. September 2011 auf und stellte fest, dass das Mietverhältnis zwischen den Parteien per 30. Juni 2010 beendet worden sei.
C. Die Mieter (Beschwerdeführer) beantragen dem Bundesgericht mit Beschwerde in Zivilsachen, das Urteil des Appellationsgerichts vom 29. September 2011 aufzuheben und festzustellen, dass die Kündigung vom 27. Mai 2010 unwirksam sei.
Die Vermieterin (Beschwerdegegnerin) schliesst auf Abweisung der Beschwerde. Die Vorinstanz nahm zu der von den Beschwerdeführern erhobenen Rüge der Überdehnung des Untersuchungsgrundsatzes gemäss <ref-law> Stellung, verzichtete im Übrigen auf Vernehmlassung und beantragte die Abweisung der Beschwerde, soweit auf sie einzutreten sei. Mit Präsidialverfügung vom 5. Januar 2012 wurde der Beschwerde die aufschiebende Wirkung erteilt.
Die Beschwerdeführer haben eine Replik eingereicht, wogegen die Beschwerdegegnerin explizit auf eine Duplik verzichtet hat.

Erwägungen:
1. 1.1 Die Vorinstanz hielt zunächst fest, das erstinstanzliche Gericht habe im Hinblick auf die Bestreitung der Aktivlegitimation der Beschwerdegegnerin durch die Beschwerdeführer zulässigerweise von sich aus das Handelsregister konsultiert. Daraus ergebe sich, dass die im Mietvertrag vom 22. Januar 1996 als Vermieterin aufgeführte Q._ AG seit dem 29. Dezember 2004 als Y._ Anlagestiftung firmiere, weshalb die Aktivlegitimation der richtig bezeichneten Beschwerdegegnerin zu Recht bejaht worden sei.
1.2 Die Beschwerdeführer rügen eine Überdehnung des Untersuchungsgrundsatzes nach <ref-law> bei der Berichtigung der Aktivlegitimation der Beschwerdegegnerin im erstinstanzlichen Verfahren. Sie machen geltend, sie hätten vorgebracht, nicht die Beschwerdegegnerin, sondern die Q._ AG sei Vermieterin, worauf die Beschwerdegegnerin entgegnet habe, die Q._ AG sei die Verwalterin, was wiederum die Beschwerdeführer bestritten hätten. Da nicht massgeblich sei, ob Unterlagen einfach oder schwierig zu beschaffen seien, gehe die Vorinstanz zu Unrecht davon aus, der erstinstanzliche Richter habe sich auf einen öffentlich zugänglichen Handelsregisterauszug stützen dürfen. Entscheidend sei, dass es einer anwaltlich vertretenen Partei zuzumuten sei, sich selbst korrekt zu bezeichnen.
1.3 Die Beschwerdeführer lassen ausser Acht, dass vorliegend keine Berichtigung einer fehlerhaften Parteibezeichnung, sondern die Überprüfung der Aktivlegitimation einer richtig bezeichneten Partei anhand des Handelsregisters erfolgte. Diese Überprüfung ist unabhängig von der Geltung der Untersuchungsmaxime zulässig, da öffentlich zugängliche Eintragungen im Handelsregister notorisch sind (Urteile 4A_645/2011 vom 27. Januar 2012 E. 3.4.2; 4A_422/2011 vom 3. Januar 2012 E. 2.3.1) und notorische Tatsachen weder behauptet noch bewiesen werden müssen (<ref-ruling> E. 4.1 mit Hinweis).
2. 2.1 Im kantonalen Verfahren war namentlich umstritten, ob die Voraussetzung des Zahlungsverzugs für eine Kündigung gemäss <ref-law> im Zeitpunkt der Kündigung erfüllt war. Die Vorinstanz bejahte dies, einerseits weil die Beschwerdeführer am 27. März 2010 nicht mehr befreiend hätten hinterlegen können, nachdem der Mangel seit dem 19. März 2010 beseitigt gewesen sei, und andererseits, weil die Hinterlegung keine Verrechnungswirkung gezeitigt habe.
2.2 Verlangt der Mieter einer unbeweglichen Sache vom Vermieter die Beseitigung eines Mangels, so muss er ihm dazu schriftlich eine angemessene Frist setzen und kann ihm androhen, dass er bei unbenütztem Ablauf der Frist Mietzinse, die künftig fällig werden, bei einer vom Kanton bezeichneten Stelle hinterlegen wird. Er muss die Hinterlegung dem Vermieter schriftlich ankündigen (<ref-law>). Mit der Hinterlegung gelten die Mietzinse als bezahlt (<ref-law>).
2.3 Soweit die Beschwerdeführer unter Berufung auf ROGER WEBER (Basler Kommentar, OR I, 4. Aufl. 2007, N. 4 zu <ref-law>) vorbringen, die Hinterlegung sei auch zur Bewirkung einer Herbsetzung des Mietzinses zulässig, ist ihnen entgegenzuhalten, dass auch dieser Autor nunmehr eine ausdehnende Interpretation von <ref-law> ablehnt, zumal die Verknüpfung des Rechts auf Hinterlegung mit dem Beseitigungsanspruch dem Wortlaut des Gesetzes entspricht (ROGER WEBER, Basler Kommentar, OR I, 5. Aufl. 2011, N. 4 zu <ref-law>). Die Verknüpfung ergibt sich aber auch aus dem Zweck Hinterlegung, die vom Gesetzgeber dem Mieter als Druckmittel zur Durchsetzung seines Anspruchs auf Mängelbeseitigung gegeben wurde (<ref-ruling> E. 2b S. 122 mit Hinweis). Die Hinterlegung steht daher zur Durchsetzung von Ansprüchen auf Mietzinsherabsetzung wegen Renovationsarbeiten nicht offen (Urteil 4A_163/2007 vom 8. August 2007 E. 4.2.1 mit Hinweisen).
2.4 Entgegen der Ansicht der Beschwerdeführer kann für die Tilgungswirkung der Hinterlegung auch nicht genügen, dass deren Voraussetzungen im Zeitpunkt ihrer Ankündigung gegeben sind. Andernfalls hätte die gesetzlich zwingend vorausgesetzte Fristansetzung, verbunden mit der Androhung der Hinterlegung bei unbenütztem Ablauf der Frist, keinen Sinn (vgl. RAYMOND BISANG UND ANDERE, Das Schweizerische Mietrecht, SVIT-Kommentar, 3. Aufl. 2008, N. 12 f. zu <ref-law>). Demnach muss der beanstandete Mangel grundsätzlich im Zeitpunkt der Hinterlegung noch bestehen, wobei nach der Rechtsprechung genügt, dass der Mieter bei der Hinterlegung gutgläubig davon ausging, es liege ein Mangel der Mietsache vor, den er weder zu vertreten noch zu beseitigen hat (<ref-ruling> E. 2b S. 122). Der bösgläubige Mieter verdient dagegen keinen Schutz vor einer Zahlungsverzugskündigung (ROGER WEBER, in: Basler Kommentar, OR I, 5. Aufl. 2011, N. 14 zu <ref-law>, mit Hinweisen).
2.5 Da die Vorinstanz - unangefochten und für das Bundesgericht verbindlich - feststellte, der bei der Androhung der Hinterlegung genannte Mangel habe im Zeitpunkt der Hinterlegung bereits seit gut einer Woche für die Beschwerdeführer erkennbar nicht mehr bestanden, konnten diese damals nicht in guten Treuen davon ausgegangen sein, es liege ein Mangel vor, den sie weder zu vertreten noch zu beseitigen hätten. Der Hinterlegung kann unter diesen Umständen keine befreiende Wirkung zugebilligt werden.
3. 3.1 Dass die Beschwerdeführer, obwohl sie noch Mietzinsherabsetzung und Rückzahlung des Heizkostenanteils beanspruchten, bis zum Zeitpunkt der Kündigung am 27. Mai 2010 keine Verrechnung dieser Forderungen mit ausstehenden Mietzinsen erklärt haben, steht fest und wird auch in der Beschwerde eingeräumt, wo lediglich erneut auf den Bestand der betreffenden Ansprüche hingewiesen wird. Die Beschwerdeführer sind jedoch der Meinung, sie seien angesichts der am 27. März 2010 erfolgten Hinterlegung des Aprilmietzinses innerhalb der ihnen am 14. April 2010 unter Kündigungsandrohung gesetzten Zahlungsfrist zu einer solchen Erklärung rechtlich gar nicht in der Lage gewesen, da ihnen mit der Hinterlegung die Dispositionsbefugnis über den Mietzins entzogen gewesen sei. Sie hätten daher zu Recht mit Schreiben vom 17. Mai 2010 darauf hingewiesen, dass die Mietzinse und auch der Aprilmietzins hinterlegt seien. Etwas anderes sei ihnen gar nicht möglich gewesen. Sollte es sich anders verhalten, läge ein Rechtsirrtum ihres Rechtsvertreters vor.
3.2 Die von den Beschwerdeführern für ihre Rechtsauffassung angegebene Stelle (PETER HIGI, Zürcher Kommentar, 3. Aufl. 1994, N. 11 zu <ref-law>), nach welcher beiden Parteien von Gesetzes wegen das direkte einseitige Verfügungsrecht über den Mietzins entzogen ist (formelle Hinterlegungswirkung), auch wenn die Hinterlegung materiell ungerechtfertigt ist, besagt nichts anderes als dass während der Hinterlegungsdauer nicht über die Hinterlage verfügt werden darf (HIGI, a.a.O., N. 66 zu <ref-law>). Dies versteht sich von selbst, muss der hinterlegte Betrag gegebenenfalls doch unbelastet dem Vermieter herausgegeben werden können. Eine Verrechnung mit der Hinterlage und eine einseitige Verfügung hierüber steht indessen nicht zur Debatte, sondern einzig mit den verrechenbaren Forderungen der Beschwerdeführer, den Ansprüchen aus Mietzinsherabsetzung und Rückzahlung des Heizkostenanteils, die sie gegenüber der Beschwerdegegnerin geltend machten. Was die Beschwerdeführer daran gehindert haben soll, diese Ansprüche der Mietzinsforderung verrechnungsweise gegenüber zu stellen, legen sie nicht dar. Dies ist auch nicht ersichtlich, zumal damit dem Entscheid über die Verwendung des hinterlegten Betrages (Art. 259h und 259i OR) nicht vorgegriffen würde. Dass ihr Rechtsvertreter betreffend die Verrechenbarkeit dieser Forderungen einem Irrtum verfallen sein soll, wird nicht behauptet. Ohnehin könnte ein allfälliger Rechtsirrtum des Rechtsvertreters der Beschwerdeführer nicht der Beschwerdegegnerin entgegengehalten werden.
4. 4.1 Die Beschwerdeführer machen schliesslich geltend, die Kündigung verstosse gegen Treu und Glauben, denn die Beschwerdegegnerin habe am 15. April 2010, als sie die Kündigung angedroht habe, gewusst oder wissen müssen, dass den Beschwerdeführern Gegenforderungen von weit mehr als einem Monatsmietzins von Fr. 2'330.-- zugestanden hätten. Darüber hinaus hätten die Beschwerdeführer zwischenzeitlich ein Verfahren bei der Schlichtungsstelle anhängig gemacht, das ja dazu dienen sollte, einen Vergleich auszuhandeln. Die Parteien hätten denn im Vergleich vom 2. Juni 2010 auch vereinbart, dass der zu Unrecht hinterlegte Mietzins, welcher den Kündigungsgrund gebildet habe, an die Mieter ausgezahlt werde. Zu beachten sei zudem, dass die Kündigung am Donnerstag, den 27. Mai 2010 und der erwähnte Vergleich am darauf folgenden Dienstag erfolgt seien. Auch unter diesem zeitlichen Aspekt sei das Interesse der Beschwerdegegnerin an der Kündigung als gering einzustufen, da praxisgemäss ein Verzug von wenigen Tagen zur Aufhebung der Zahlungsverzugskündigung führen müsse. Dies erst recht, wenn man bedenke, dass der Mietzins ja nicht ausgeblieben, sondern sicher hinterlegt worden sei. Es gehe nicht an, einerseits einen Vergleich abzuschliessen, gemäss welchem die hinterlegten Mietzinse dem Mieter zustünden und andererseits zu behaupten, die Hinterlegung sei zu Unrecht erfolgt.
4.2 Nach <ref-law> ist die Kündigung anfechtbar, wenn sie gegen den Grundsatz von Treu und Glauben verstösst. Allgemein gilt, dass eine Kündigung treuwidrig ist, wenn sie ohne objektives, ernsthaftes und schützenswertes Interesse ausgesprochen wird (<ref-ruling> E. 4a S. 32 f.; <ref-ruling> E. 3a S. 108; vgl. auch Urteil 4C.267/2002 vom 18. November 2002 E. 2.2, in: SJ 2003 I S. 261 ff., 263). Auch eine wegen Zahlungsverzugs ausgesprochene ausserordentliche Kündigung kann missbräuchlich im Sinne von <ref-law> sein. Allerdings bedarf es hierzu besonderer Umstände (<ref-ruling> E. 4a S. 33). Solche können vorliegen, wenn der ausstehende Betrag unbedeutend war oder kurze Zeit nach Ablauf der Zahlungsfrist geleistet wurde und der Mieter den Mietzins zuvor immer rechtzeitig bezahlt hatte (Urteil 4A_585/2010 vom 2. Februar 2011 E. 4.1 mit Hinweisen). Auch wurde eine Kündigung als missbräuchlich qualifiziert, die der Vermieter angedroht hatte, bevor er über die rückständigen Beträge Gewissheit erlangt hatte, weshalb er die Bezahlung eines wesentlich übersetzten Betrages einforderte (<ref-ruling> E. 4b S. 33 f.). Ausserdem wurde eine Kündigung als treuwidrig aufgehoben, die der Vermieter androhte, während die Parteien über eine grundsätzlich unbestrittene Mietzinsreduktion verhandelten, deren Höhe im Zeitpunkt der Androhung und Erklärung der Kündigung höchst unklar war (Urteil 4C.65/2003 vom 23. September 2003, E. 4.2; vgl. auch Urteil 4C.2/2007 vom 20. März 2007 E. 4.2). Ebenso erachtete das Bundesgericht eine Zahlungsverzugskündigung des Vermieters eines sowohl vor als auch während der Nachfrist mangelhaften Mietobjekts für treuwidrig, der ursprünglich versprochen hatte, eine Entschädigung im Laufe der Ursache der Mängel bildenden Bauarbeiten auszuzahlen, die Zahlung dann aber bis zu deren Abschluss aufschob und sich der erklärten Verrechnungsabsicht der Mieterin, welche über den versprochenen Entschädigungsbetrag im Unklaren war, ohne Angabe von Gründen widersetzte und es auch ablehnte, sein Entschädigungsangebot zu beziffern (Urteil 4C.173/2005 vom 24. Oktober 2005 E. 2.3).
4.3 Von diesen Konstellationen weicht die zu beurteilende insbesondere dadurch ab, dass sich die Beschwerdeführer selbst treuwidrig verhielten, indem sie den Mietzins hinterlegten, obwohl sie wussten, dass die Beschwerdegegnerin den Anlass zur Hinterlegung bildenden Mangel innert der angesetzten Frist behoben hatte. Ausserdem verfügten sie nach eigenen Angaben über Forderungen gegenüber der Vermieterschaft, welche den Mietzins, mit dem sie säumig waren, weit überstiegen. Dennoch stellten sie diese nicht zur Verrechnung, sondern zogen es vor, auf ihrem Hinterlegungsrecht zu beharren. Die nachfolgende Zahlungsverzugskündigung des Vermieters als treuwidrig zu betrachten würde darauf hinaus laufen, der treuwidrig erfolgten Hinterlegung Tilgungswirkung zu verleihen. <ref-law> bezweckt aber nicht den Rechtsschutz jener Partei, die sich selbst treuwidrig verhalten hat. Ebenso wenig soll dem Mieter über <ref-law> faktisch ein gesetzlich nicht vorgesehenes Recht in die Hand gegeben werden, zwischen Hinterlegung und Verrechnung frei zu wählen. Schliesslich zeigen die Beschwerdeführer mit ihren Ausführungen zur zeitlichen Nähe zwischen der Kündigung vom 27. Mai 2010 und dem am 2. Juni 2010 abgeschlossenen Vergleich nicht auf, inwiefern der ausstehende Mietzins kurz nach Ablauf der Zahlungsfrist beglichen worden sein soll, was auch nicht ersichtlich ist. Die Vorinstanz verletzte somit kein Bundesrecht, wenn sie die von der Beschwerdegegnerin ausgesprochene Kündigung nicht als gegen Treu und Glauben verstossend einstufte.
5. Aus den dargelegten Gründen erweist sich die Beschwerde als unbegründet und ist abzuweisen. Bei diesem Ausgang des bundesgerichtlichen Verfahrens werden die Beschwerdeführer dafür unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 2 und 5 BGG, Art. 68 Abs. 1 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 3'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 3. April 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Gelzer