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 Art. 257d OR. 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 Art. 274d OR 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.