Sachverhalt: A. Mit Vertrag vom 14./27. Oktober 1997 mieteten A. und B. X._ (Beschwerdeführer) von C._ (Beschwerdegegner) eine 5,5-Zimmerwohnung in Basel. Der ursprünglich bis zum 31. Januar 2003 abgeschlossene Mietvertrag wurde mit Nachtrag vom 29. Januar 2003 um 5 Jahre verlängert, und es wurde vereinbart, das Mietverhältnis solle bis zum 31. Januar 2013 dauern, falls es nicht von einer Partei ein Jahr vor Ablauf der festen Vertragsdauer gekündigt werde. Da keine Kündigung erfolgte, trat die Verlängerung ein. Am 30. Januar 2008 eröffneten die Beschwerdeführer dem Beschwerdegegner ihre Absicht, die Liegenschaft zu verlassen. Da sich die Parteien nicht über eine vorzeitige Vertragsauflösung einigen konnten, suchten die Beschwerdeführer einen möglichen Nachmieter, als welcher sich D._ präsentierte. Er bekräftigte anlässlich einer Besprechung mit den Parteien und einer Mitarbeiterin des Vermieters am 12. Dezember 2008 sein Mietinteresse. Mit E-Mail vom 17. Dezember 2008 teilte er jedoch den Beschwerdeführern mit, er ziehe sein Mietinteresse an der Wohnung zurück und entscheide sich statt dessen für eine Alternative. Am Tag darauf stellte ihm die Mitarbeiterin des Vermieters den ausstehenden Mietvertragsentwurf zu. Ein Mietvertrag mit D._ kam jedoch nicht zustande. B. In der Folge nahmen die Beschwerdeführer den Standpunkt ein, sie hätten mit befreiender Wirkung im Sinne von Art. 264 Abs. 1 OR in der Person von D._ einen Nachmieter gestellt. Nach erfolglosem Schlichtungsverfahren gelangten sie am 7. Mai 2009 an das Zivilgericht Basel-Stadt mit dem Rechtsbegehren, es sei festzustellen, dass die Mieterschaft von den Verpflichtungen aus dem Mietvertrag befreit sei, da sie auf den 1. März 2009 eine objektiv zumutbare Ersatzmieterschaft gestellt habe. Das Zivilgericht hiess die Feststellungsklage mit Urteil vom 15. April 2010 gut und stellte fest, die Klagpartei sei ab dem Monat März 2009 von den Verpflichtungen gemäss Art. 257 ff. OR für die vom Beschwerdegegner gemietete Wohnung gemäss Mietvertrag vom 14./27. Oktober 1997 befreit. Der Beschwerdegegner focht dieses Urteil beim Appellationsgericht des Kantons Basel-Stadt an, welches mit Urteil vom 4. April 2011 seine Beschwerde guthiess, das Urteil des Zivilgerichts aufhob und die Klage abwies. C. Die Beschwerdeführer beantragen dem Bundesgericht mit Beschwerde in Zivilsachen, das angefochtene Urteil aufzuheben und festzustellen, dass die Mieterschaft ab März 2009 von den Verpflichtungen aus dem Mietvertrag befreit sei, da sie auf den 1. März 2009 eine objektiv zumutbare Ersatzmieterschaft gestellt habe. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Dem Gesuch um Gewährung der aufschiebenden Wirkung gab das Bundesgericht am 16. Dezember 2011 statt. Der Beschwerdegegner schliesst auf kostenfällige Abweisung der Beschwerde, soweit darauf einzutreten sei, während das Appellationsgericht beantragt, auf die Beschwerde nicht einzutreten, eventuell diese abzuweisen. Die Beschwerdeführer haben unaufgefordert eine Replik eingereicht.