Sachverhalt: A. A.a A._ und B._ (Beschwerdeführer) mieteten von C._ (Beschwerdegegner) ab dem 1. Oktober 2000 in der Liegenschaft D.i._ eine 5-Zimmer-Wohnung im 1. Stock, einen Abstellraum im Erdgeschoss und zwei Garagenplätze. Zusätzlich wurde unter anderem auch die Mitbenutzung der Garage, des Schwimmbades, des Fitnessraums sowie der Sauna vereinbart. Der Mietzins wurde auf Fr. 7'300.-- netto bzw. Fr. 8'200.-- brutto pro Monat angesetzt und ist indexiert. Mit amtlichem Formular vom 28. Oktober 2003 wurde der Mietzins per 1. Januar 2004 auf Fr. 7'472.-- netto bzw. Fr. 8'393.-- brutto pro Monat angehoben. A.b Seit dem 6. September 2004 wird das an der Strasse D.i.i._ gelegene Hotel X._ umgebaut. Am 24. November 2004 sandten die Beschwerdeführer ein Schreiben "zur Kenntnisnahme" an den Beschwerdegegner. Darin hielten sie fest, dass seit Anfang der Bauarbeiten des Hotels X._ in und um ihre Mietwohnung unzumutbare Umstände herrschten. Sie würden täglich von 7:00 Uhr morgens bis spät abends, fast jeden Samstag und auch schon nachts, durch ständigen grossen Lärm gestört. Dazu kämen Schmutz und Staub, eine Verunstaltung der Umgebung und Aussicht sowie eine fragwürdige Sicherheit (die Baustelle werde nachts zum Spielplatz, auch Baumaterialien landeten auf der Strasse). Ausserdem seien die total verdreckten Zufahrtsstrassen zu ihrer Wohnung ständig mit Lastwagen versperrt. Mit Schreiben vom 31. August 2005 teilte der damalige Rechtsvertreter von A._ dem Beschwerdegegner mit, seine Mandantschaft habe ihn darüber informiert, dass seit dem 6. September 2004 bis voraussichtlich Ende Dezember 2007 auf dem gegenüberliegenden Grundstück das Hotel X._ vollständig renoviert werde. Er habe sich selber durch einen Augenschein von den massiven Lärm- und Staubimmissionen überzeugt. Seine Mandantschaft habe den Beschwerdegegner bereits mit Schreiben vom 24. November 2004 darüber in Kenntnis gesetzt. Er müsse (auch) davon ausgehen, dass der Beschwerdegegner als im Quartier X._ wohnender Anlieger vom Beginn der Bauarbeiten am 6. September 2004 Kenntnis genommen habe. Die ARGE Hotel X._ habe die Anwohner mit Schreiben vom 2. September 2004 über die bevorstehenden Baumeisterarbeiten informiert. A._ mache gegenüber dem Beschwerdegegner unter Berufung auf Art. 259d OR einen Herabsetzungsanspruch des Nettomietzinses von 80 % geltend, was bei einem Nettomietzins von Fr. 7'472.-- pro Monat einen Senkungsanspruch von Fr. 5'977.60 pro Monat ergebe. Demzufolge schulde der Beschwerdegegner bis Ende August 2005, beginnend ab September 2004, insgesamt Fr. 71'731.20, die bis spätestens 30. September 2005 auf das angegebene Konto einzuzahlen seien. A.c Der Beschwerdegegner bestritt die geltend gemachten Ansprüche. A._ betrieb den Beschwerdegegner daraufhin mit Zahlungsbefehl vom 21. November 2005 über Fr. 71'731.20 nebst Zins zu 5 % seit 1. Oktober 2005, wogegen der Beschwerdegegner am 22. November 2005 Rechtsvorschlag erhob. B. B.a Mit Eingabe vom 9. Dezember 2005 an die Schlichtungsbehörde des Bezirks Zürich leitete A._ gegen den Beschwerdegegner Klage ein. Der Beschwerdegegner liess der Schlichtungsbehörde in der Folge mitteilen, er habe der Hotel X._ AG (Bauherrin des Hotels X._) den Streit verkündet. Die Hotel X._ AG teilte der Schlichtungsbehörde daraufhin mit, dem Prozess als Nebenintervenientin beitreten zu wollen. Nachdem sich die Parteien in der Schlichtungsverhandlung nicht hatten einigen können, liess A._ die Klage fristgerecht an das Mietgericht Zürich prosequieren. Er beantragte, es sei der Beschwerdegegner zu verpflichten, den Mietzins von Fr. 7'472.-- monatlich beginnend ab September 2004 um 80 % pro Monat bis zur vollständigen Beendigung der Bauarbeiten herabzusetzen. Der Beschwerdegegner sei ferner zur Zahlung von Fr. 71'731.20 nebst 5 % Zins seit 1. Oktober 2005 zu verpflichten. Zudem sei im eingeleiteten Betreibungsverfahren der Rechtsvorschlag zu beseitigen. Das Mietgericht Zürich wies die Klage mit Urteil vom 21. März 2007 ab. B.a Im Berufungsverfahren liess das Obergericht den von den Beschwerdeführern beantragten Parteiwechsel zu und nahm beide Beschwerdeführer als Kläger ins Rubrum auf. Die von den Beschwerdeführern gegen das mietgerichtliche Urteil erhobene Berufung wies das Obergericht des Kantons Zürich hingegen mit Entscheid vom 26. Oktober 2007 ab. B.b Gegen das obergerichtliche Urteil erhoben die Beschwerdeführer am 5. Dezember 2007 Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich. Statt die Beschwerde zu begründen, beschränkten sich die Beschwerdeführer zunächst darauf, ein Gesuch um erstmalige Erstreckung der Frist zur Begründung der Beschwerde bis 4. Januar 2008 zu stellen. Mit Präsidialverfügung vom 6. Dezember 2007 wurde das Fristerstreckungsgesuch abgewiesen. Daraufhin stellten die Beschwerdeführer mit Datum vom 20. Dezember 2007 ein Gesuch um Wiederherstellung der Frist zur Begründung der Nichtigkeitsbeschwerde, dem sich sowohl der Beschwerdegegner als auch die Nebenintervenientin widersetzten. Mit Zirkulationsbeschluss vom 31. März 2008 wies das Kassationsgericht das Gesuch der Beschwerdeführer um Wiederherstellung der Frist zur Begründung der Nichtigkeitsbeschwerde ab und trat auf die Beschwerde mangels rechtsgenügender Begründung nicht ein. Das Mietgericht Zürich wies die Klage mit Urteil vom 21. März 2007 ab. B.a Im Berufungsverfahren liess das Obergericht den von den Beschwerdeführern beantragten Parteiwechsel zu und nahm beide Beschwerdeführer als Kläger ins Rubrum auf. Die von den Beschwerdeführern gegen das mietgerichtliche Urteil erhobene Berufung wies das Obergericht des Kantons Zürich hingegen mit Entscheid vom 26. Oktober 2007 ab. B.b Gegen das obergerichtliche Urteil erhoben die Beschwerdeführer am 5. Dezember 2007 Nichtigkeitsbeschwerde an das Kassationsgericht des Kantons Zürich. Statt die Beschwerde zu begründen, beschränkten sich die Beschwerdeführer zunächst darauf, ein Gesuch um erstmalige Erstreckung der Frist zur Begründung der Beschwerde bis 4. Januar 2008 zu stellen. Mit Präsidialverfügung vom 6. Dezember 2007 wurde das Fristerstreckungsgesuch abgewiesen. Daraufhin stellten die Beschwerdeführer mit Datum vom 20. Dezember 2007 ein Gesuch um Wiederherstellung der Frist zur Begründung der Nichtigkeitsbeschwerde, dem sich sowohl der Beschwerdegegner als auch die Nebenintervenientin widersetzten. Mit Zirkulationsbeschluss vom 31. März 2008 wies das Kassationsgericht das Gesuch der Beschwerdeführer um Wiederherstellung der Frist zur Begründung der Nichtigkeitsbeschwerde ab und trat auf die Beschwerde mangels rechtsgenügender Begründung nicht ein. C. Mit Beschwerde in Zivilsachen vom 8. Mai 2008 beantragen die Beschwerdeführer im Wesentlichen die Aufhebung des obergerichtlichen Entscheids vom 26. Oktober 2007 sowie die Gutheissung ihrer Klagebegehren, eventualiter die Rückweisung zur Neubeurteilung an das Obergericht. Sowohl der Beschwerdegegner als auch die Nebenintervenientin schliessen auf kostenfällige Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das Obergericht hat auf eine Vernehmlassung verzichtet. Das Kassationsgericht weist in seiner Vernehmlassung darauf hin, dass die Beschwerdeführer einzig die Aufhebung des Beschlusses des Obergerichts vom 26. Oktober 2007 verlangen, während sie den Zirkulationsbeschluss des Kassationsgerichts vom 31. März 2008 nicht anfechten, weshalb sich weitere Ausführungen zur Beschwerde erübrigten.