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.

Erwägungen:
1. Gibt der Mieter die Sache zurück, ohne Kündigungsfrist oder -termin einzuhalten, so ist er von seinen Verpflichtungen gegenüber dem Vermieter nur befreit, wenn er einen für den Vermieter zumutbaren neuen Mieter vorschlägt; dieser muss zahlungsfähig und bereit sein, den Mietvertrag zu den gleichen Bedingungen zu übernehmen (Art. 264 Abs. 1 OR). Die Vorinstanz liess offen, ob es sich bei D._ um einen zumutbaren Mieter handelte und ob er vom Beschwerdegegner als solcher akzeptiert worden war. Sie kam in eingehender Beweiswürdigung zum Schluss, D._ habe es an der Bereitschaft gefehlt, den Mietvertrag zu übernehmen. Namentlich aus dem Umstand, dass D._ noch im Februar 2010, mithin über ein Jahr nach den Ereignissen vom Dezember 2008, an seiner alten Adresse vorgeladen werden konnte, folgerte die Vorinstanz, er habe entgegen seiner Erklärung keinen anderen Mietvertrag angenommen. Es sei anzunehmen, er hätte sich bei fortbestehendem Interesse die Gelegenheit zur Nachmiete nicht entgehen lassen, nachdem sich die Gespräche mit dem behaupteten Alternativvermieter, der bis zum 19. Dezember 2008 eine Zusage verlangt haben soll, zerschlagen hätten.
1.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhaltes kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5 S. 130, 397 E. 1.5 S. 401; <ref-ruling> E. 1.2.2 S. 252).
1.2 Willkürlich ist ein Entscheid nach konstanter Rechtsprechung nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür vielmehr nur auf, wenn er offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Dabei genügt es nicht, wenn sich nur die Begründung des angefochtenen Entscheides als unhaltbar erweist. Eine Aufhebung rechtfertigt sich nur dann, wenn der Entscheid auch im Ergebnis verfassungswidrig ist (<ref-ruling> E. 2.2.2 S. 318 f.; <ref-ruling> E. 2.1 S. 9).
1.3 Der Beschwerdeführer, der die Sachverhaltsfeststellungen der Vorinstanz anfechten will, kann sich nicht damit begnügen, den bestrittenen Feststellungen eigene tatsächliche Behauptungen gegenüberzustellen oder darzulegen, wie die Beweise seiner Ansicht nach zu würdigen gewesen wären. Vielmehr hat er klar und substanziiert aufzuzeigen, inwiefern die gerügten Feststellungen bzw. die Unterlassung von Feststellungen offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruhen. Auf eine Kritik an den tatsächlichen Feststellungen der Vorinstanz, die diesen Anforderungen nicht genügt, ist nicht einzutreten (BGE <ref-ruling> E. 1.4.3 S. 254 f.; <ref-ruling> E. 2.4 S. 466 f.).
1.4 Soweit Willkür in der Ermittlung des Sachverhalts geltend gemacht wird, ist zu beachten, dass dem Sachrichter in der Beweiswürdigung ein breiter Ermessensspielraum zusteht; der Beschwerdeführer hat daher nach Massgabe von Art. 106 Abs. 2 BGG darzulegen, inwiefern das kantonale Gericht sein Ermessen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse gezogen, erhebliche Beweise übersehen oder willkürlich ausser Acht gelassen habe (BGE <ref-ruling> E. 2.1 S. 9; <ref-ruling> E. 1b S. 30). Dagegen genügt es nicht, wenn der Beschwerdeführer lediglich einzelne Beweise anführt, die er anders als im angefochtenen Entscheid gewichtet wissen möchte.
1.5 Die Beschwerdeführer werfen der Vorinstanz vor, bei der Beweiswürdigung in Willkür verfallen zu sein. Zur Begründung führen sie an, die Vorinstanz hätte durch eine persönliche Befragung der Parteien und durch erneute Befragung von D._ als Zeugen die Ungereimtheiten, aus welchen sie dessen Unglaubwürdigkeit ableitete, überprüfen müssen.
1.5.1 Mit dem Hinweis darauf, allfällige Widersprüche hätten sich unter Umständen durch weitere Befragungen auflösen lassen, kommen die Beschwerdeführer indessen ihrer Obliegenheit nicht nach, im Einzelnen aufzuzeigen, inwiefern die Vorinstanz bei der Würdigung der bereits erhobenen Beweise in Willkür verfallen ist. Dass das Zivilgericht die Beweise noch anders gewürdigt hat, genügt nicht, um Willkür in der Beweiswürdigung der Vorinstanz aufzuzeigen. Insoweit genügt die Beschwerde den Begründungsanforderungen nicht.
1.5.2 Zudem räumen die Beschwerdeführer selbst ein, dass D._ mit dem offenbar auf raschen Abschluss drängenden anderen Vermieter schliesslich kein Mietverhältnis begründet hat. Wäre der von den Beschwerdeführern gestellte Nachmieter tatsächlich zur Übernahme der Wohnung bereit gewesen, ist nicht nachvollziehbar, weshalb er unter den gegebenen Umständen nicht auf das Angebot des Beschwerdegegners zurückkam und sich um den Abschluss des vorbesprochenen Mietvertrages bemüht hat. Wenn die Vorinstanz vor diesem Hintergrund davon ausging, in Wirklichkeit habe D._ die Bereitschaft zur Übernahme der von den Beschwerdeführern gemieteten Wohnung gefehlt, erweist sich dieser Rückschluss auch ohne erneute Befragung nicht als unhaltbar. Es ist nicht willkürlich, wenn die Vorinstanz im Ergebnis davon ausgeht, angesichts der Umstände hätte selbst eine im Sinne der Beschwerdeführer lautende Aussage von D._ nichts mehr an der Überzeugung des Gerichts zu ändern vermocht.
1.5.3 Da die Vorinstanz willkürfrei von der fehlenden Bereitschaft von D._ zur Übernahme der von den Beschwerdeführern gemieteten Wohnung ausgehen durfte, ist nicht entscheiderheblich, ob der Beschwerdegegner D._ als Ersatzmieter akzeptiert hätte. Auf die diesbezüglichen Vorbringen ist daher nicht einzugehen.
2. Aus den dargelegten Gründen erweist sich die Beschwerde als unbegründet und ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang werden die Beschwerdeführer unter solidarischer Haftbarkeit für das bundesgerichtliche Verfahren kosten- und entschädigungspflichtig.

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