Sachverhalt:
A. Mit Beschluss vom 8. November 2005 verweigerte die Bausektion der Stadt Zürich die nachträgliche baurechtliche Bewilligung für die sexgewerbliche Nutzung der Lokalitäten im Untergeschoss, Erdgeschoss sowie 1. und 4. Obergeschoss der im Eigentum der Rehe AG stehenden Liegenschaft Dienerstrasse 2 in Zürich (Grundstück Kat.-Nr. AU 4882). A._, B._, C._ und weiteren namentlich genannten Personen als Mieterschaften sowie allen Rechtsnachfolgerinnen und -nachfolgern wurde befohlen, bis spätestens drei Monate ab Rechtskraft des Entscheids die sexgewerbliche Nutzung der von ihnen gemieteten Räume zu beenden, die Lokalitäten zu räumen und dafür besorgt zu sein, dass allfällige sich darin befindliche Drittpersonen, insbesondere Prostituierte, die Räume verlassen.
Nachdem dieser Entscheid in Rechtskraft erwachsen war, forderte das Hochbaudepartement der Stadt Zürich die Rehe AG mit Schreiben vom 20. April 2007 auf, sämtliche betroffenen Mietverhältnisse aufzulösen und die fraglichen Lokalitäten zu räumen. Darauf stellten A._, B._, C._ sowie die D._ GmbH am 27. Mai 2007 ein Wiedererwägungs- und Revisionsgesuch wegen behaupteter Entdeckung von Verfahrensmängeln. Die Bausektion der Stadt Zürich trat mit Beschluss vom 10. Juli 2007 auf das Gesuch nicht ein.
B. Gegen den Beschluss vom 10. Juli 2007 reichten A._, B._, C._ sowie die D._ GmbH Rekurs bei der Baurekurskommission des Kantons Zürich ein und verlangten die Aufhebung des Nichteintretensentscheids. Mit Entscheid vom 13. März 2008 wies die Baurekurskommission den Rekurs ab.
In der Folge erhoben A._, B._, C._ sowie die D._ GmbH Beschwerde beim Verwaltungsgericht des Kantons Zürich. Sie beantragten die Aufhebung des angefochtenen Entscheids; eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Mit Entscheid vom 20. August 2008 wies das Verwaltungsgericht die Beschwerde ab. Es erwog, der Bauentscheid vom 8. November 2005 sei mit einer korrekten Rechtsmittelbelehrung zugestellt worden. Damit seien die betroffenen Mieter in das Verfahren einbezogen worden, weshalb kein Revisionsgrund vorliege.
C. Mit Eingabe vom 7. Oktober 2008 erheben A._, B._, C._ sowie die D._ GmbH beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>). Sie beantragen die Feststellung des Vorliegens eines Revisionsgrundes, die Aufhebung des verwaltungsgerichtlichen Entscheids vom 20. August 2008 und die Rückweisung der Sache zur Neubeurteilung an die Vorinstanz. Sie rügen eine Verletzung der Verfahrensgarantien gemäss Art. 18 Abs. 2 KV/ZH (SR 131.211) sowie der Grundsätze rechtsstaatlichen Handelns (<ref-law>), der Rechtsgleichheit (<ref-law>), des Willkürverbots und des Grundsatzes von Treu und Glauben (<ref-law>) sowie ihres Anspruchs auf ein gerechtes Verfahren und auf rechtliches Gehör (Art. 29 Abs. 1 und 2 BV).
D. Das Verwaltungsgericht und die Bausektion der Stadt Zürich schliessen in ihren Vernehmlassungen auf Abweisung der Beschwerde. Die Beschwerdeführer haben von der Gelegenheit eine Replik einzureichen Gebrauch gemacht. Mit Eingabe vom 19. Januar 2009 halten sie an ihren bisherigen Ausführungen und Anträgen fest.

Erwägungen:
1. 1.1 Das angefochtene Urteil des Verwaltungsgerichts ist ein Endentscheid einer letzten kantonalen Instanz (<ref-law>). Ihm liegt ein Beschwerdeverfahren über ein Gesuch um Revision eines baurechtlichen Entscheids und damit eine öffentlich-rechtliche Angelegenheit zu Grunde. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> steht auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Ein Ausschlussgrund nach <ref-law> liegt nicht vor (vgl. <ref-ruling> E. 1.2 S. 251, 409 E. 1.1 S. 411).
1.2 Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen und sind Mieter der vom Bauentscheid vom 8. November 2005 betroffenen Lokalitäten an der Dienerstrasse 2 in Zürich. Sie sind vom angefochtenen Entscheid besonders berührt und berufen sich auf schutzwürdige Interessen. Ihre Beschwerdelegitimation ist gestützt auf <ref-law> zu bejahen (vgl. <ref-ruling> E. 1.3 S. 252 ff., 353 E. 3.1 S. 357).
1.3 Die übrigen Sachurteilsvoraussetzungen geben zu keinen weiteren Bemerkungen Anlass. Vorbehältlich genügend begründeter Rügen (vgl. Art. 106 Abs. 2 i.V.m. <ref-law>) ist daher auf die Beschwerde einzutreten.
2. 2.1 Die Beschwerdeführer machen geltend, die Vorinstanz habe ihren Anspruch auf rechtliches Gehör verletzt, indem sie sich nicht damit auseinandergesetzt habe, ob sie nicht von Anfang an in das baurechtliche Verfahren, das zum Bauentscheid vom 8. November 2005 geführt hatte, als Partei hätten miteinbezogen werden müssen. Von diesem Verfahren seien sie als Mieter existentiell betroffen, da es um die Frage der Zulässigkeit der Nutzung der von ihnen gemieteten Räume gehe.
2.2 In ihrer Eingabe vom 21. April 2008 an die Vorinstanz halten die Beschwerdeführer fest, die verbliebene, noch zu beantwortende Rechtsfrage konzentriere sich auf die Problematik, ob ihnen die Berechtigung gegen den Bauentscheid vom 8. November 2005 ein Rechtsmittel zu ergreifen, in rechtsgenüglich erkenntlicher Weise kommuniziert worden sei (Beschwerdeschrift, S. 3). Ihre Ausführungen sind dementsprechend gänzlich auf dieses Thema ausgerichtet und sie behandeln dabei auch die Frage der Beteiligung am erstinstanzlichen Verfahren in diesem Rahmen und heben sie nicht eigens hervor. Unter diesen Umständen ist unter dem Gesichtswinkel des rechtlichen Gehörs nicht zu beanstanden, dass sich die Vorinstanz ebenfalls in erster Linie mit den an die Rechtsmittelbelehrung gestellten Anforderungen auseinandergesetzt hat und daneben nicht noch eingehend prüfte, ob die Beschwerdeführer am erstinstanzlichen Verfahren als Parteien hätten beteiligt werden müssen. Die Rüge der Verletzung des rechtlichen Gehörs ist daher nicht stichhaltig.
3. 3.1 Die Beschwerdeführer machen zudem geltend, als Laien hätten sie nicht erkannt, dass ihnen gegen den Bauentscheid vom 8. November 2005, der ihnen Ende Dezember 2005 bzw. anfangs Januar 2006 zugestellt worden sei, eine Rekursmöglichkeit zugestanden habe. Dies sei ihnen erst bewusst geworden, nachdem sie im Frühjahr 2007 zum Verlassen der Wohnungen aufgefordert worden seien und sie deshalb rechtliche Erkundigungen eingeholt hätten. Indem sie in diesem Entscheid nicht mit ausreichender Klarheit darauf hingewiesen worden seien, dass sie dagegen auch als bisher am Verfahren nicht beteiligte Partei Rekurs erheben können, seien die Verfahrensgarantie gemäss Art. 18 Abs. 2 KV/ZH sowie der Anspruch auf ein gerechtes Verfahren und auf rechtliches Gehör (Art. 29 Abs. 1 und 2 BV) verletzt worden. Ein solches Vorgehen widerspreche zudem dem Grundsatz von Treu und Glauben (<ref-law>). Darüber hinaus sei es rechtsungleich, diskriminierend und willkürlich, wenn mit einer Rechtsmittelbelehrung gegenüber einer am Verfahren beteiligten Partei Klarheit geschaffen werde, während damit eine am Verfahren nicht direkt beteiligte Person, bei der es sich um eine mögliche Partei im Rechtsmittelverfahren handle und die von den Folgen des betreffenden Entscheids in existenzieller Weise betroffen sei, bezüglich ihrer Rechtsmittelmöglichkeiten im Dunkeln gelassen werde. Rechtsungleich und diskriminierend sei ferner, im Mietrecht zum Schutz der Mieter höchste Anforderungen an die Aufklärung der Mieter über deren Rechte und die möglichen Rechtsmittel insbesondere bei einer Beendigung des Mietverhältnisses zu stellen (Kündigungsformulare) und andererseits bei baurechtlichen Entscheiden wie dem vorliegenden, welche die Mieter gleicherweise betreffen, da sie die gemieteten Räumlichkeiten verlassen müssen, nicht den selben Standard wie bei einer Kündigung einzuhalten und von einer klaren Orientierung über die Rechtsmittelmöglichkeiten abzusehen.
3.2 Die Vorinstanz führt aus, die Parteien hätten nach Art. 18 Abs. 2 KV/ZH Anspruch auf einen begründeten Entscheid mit Rechtsmittelbelehrung. Diese müsse nach § 10 Abs. 2 des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959 (VRG; LS 175.2) das zulässige ordentliche Rechtsmittel, die Rechtsmittelinstanz und die Rechtsmittelfrist bezeichnen. Die Rechtsmittelbelehrung in Dispositiv Ziffer VI. des Bauentscheids vom 8. November 2005 genüge diesen Anforderungen. Weitergehende Angaben etwa über die zur Erhebung eines Rechtsmittels Berechtigten seien weder erforderlich noch möglich. Über die Legitimation entscheide nicht die verfügende Behörde, sondern die Rechtsmittelinstanz. Zudem könne die Beschwerdeberechtigung auch von den geltend gemachten Rügen abhängen. Im Übrigen sei aus Dispositiv Ziffer III.2 des Bauentscheids vom 8. November 2005 klar erkennbar, dass dieser die Mieterschaft unmittelbar verpflichte, bis spätestens drei Monate ab Rechtskraft des Beschlusses die sexgewerbliche Nutzung zu beenden und die Lokalitäten zu räumen. Ein legitimationsbegründendes Berührtsein der Mieterschaft liege somit auch für Laien erkennbar auf der Hand. Indem der mit einer korrekten Rechtsmittelbelehrung versehene Bauentscheid vom 8. November 2005 den Beschwerdeführern zugestellt worden sei, liege kein Verfahrensfehler vor. Eine Revision rechtfertige sich daher nicht.
3.2 Die Vorinstanz führt aus, die Parteien hätten nach Art. 18 Abs. 2 KV/ZH Anspruch auf einen begründeten Entscheid mit Rechtsmittelbelehrung. Diese müsse nach § 10 Abs. 2 des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959 (VRG; LS 175.2) das zulässige ordentliche Rechtsmittel, die Rechtsmittelinstanz und die Rechtsmittelfrist bezeichnen. Die Rechtsmittelbelehrung in Dispositiv Ziffer VI. des Bauentscheids vom 8. November 2005 genüge diesen Anforderungen. Weitergehende Angaben etwa über die zur Erhebung eines Rechtsmittels Berechtigten seien weder erforderlich noch möglich. Über die Legitimation entscheide nicht die verfügende Behörde, sondern die Rechtsmittelinstanz. Zudem könne die Beschwerdeberechtigung auch von den geltend gemachten Rügen abhängen. Im Übrigen sei aus Dispositiv Ziffer III.2 des Bauentscheids vom 8. November 2005 klar erkennbar, dass dieser die Mieterschaft unmittelbar verpflichte, bis spätestens drei Monate ab Rechtskraft des Beschlusses die sexgewerbliche Nutzung zu beenden und die Lokalitäten zu räumen. Ein legitimationsbegründendes Berührtsein der Mieterschaft liege somit auch für Laien erkennbar auf der Hand. Indem der mit einer korrekten Rechtsmittelbelehrung versehene Bauentscheid vom 8. November 2005 den Beschwerdeführern zugestellt worden sei, liege kein Verfahrensfehler vor. Eine Revision rechtfertige sich daher nicht.
3.3 3.3.1 Der angefochtene Entscheid stützt sich in der Sache auf kantonales Recht. Er kann vom Bundesgericht insbesondere darauf überprüft werden, ob er Bundesrecht (<ref-law>) oder kantonale verfassungsmässige Rechte verletzt (<ref-law>). Vorliegend ist daher zu prüfen, ob die Vorinstanz mit der Begründung, beim Bauentscheid vom 8. November 2005 liege eine korrekte Rechtsmittelbelehrung vor, sodass kein Verfahrensfehler gegeben sei, der einen Revisionsgrund darstellen könnte, gegen die Verfahrensgarantie gemäss Art. 18 Abs. 2 KV/ZH verstossen hat.
3.3.2 Nach Art. 18 Abs. 2 KV/ZH haben Parteien Anspruch auf einen begründeten Entscheid mit Rechtsmittelbelehrung. Welche Elemente die Rechtsmittelbelehrung im Einzelnen umfassen muss, wird in der Kantonsverfassung nicht näher ausgeführt. Zur Auslegung kann daher die kantonale Verwaltungsrechtspflegegesetzgebung herangezogen werden, wonach eine Rechtsmittelbelehrung das zulässige Rechtsmittel, die Rechtsmittelinstanz und die Rechtsmittelfrist bezeichnen muss (§ 10 Abs. 2 VRG). Ferner sieht auch das Bundesgesetz vom 20. Dezember 1968 über das Verwaltungsverfahren (SR 172.021; im Folgenden: VwVG) für seinen Anwendungsbereich keine weiter gehenden Anforderungen an den Inhalt einer Rechtsmittelbelehrung vor (vgl. <ref-law>). Keine der erwähnten Gesetzgebungen kennt überdies unterschiedliche Anforderungen an den Inhalt einer Rechtsmittelbelehrung, je nach dem in Frage stehenden Rechtsgebiet oder je nach der Parteistellung des Betroffenen. Somit ergibt sich, dass für den vorliegenden Fall, bei dem Mieter von einer baurechtlichen Anordnung unmittelbar betroffen sind, gestützt auf Art. 18 Abs. 2 KV/ZH keine weiter gehenden Anforderungen an den Inhalt der Rechtsmittelbelehrung gestellt werden können, als dass diese das zulässige Rechtsmittel, die Rechtsmittelinstanz und die Rechtsmittelfrist bezeichnen muss.
Die Rechtsmittelbelehrung des Bauentscheids vom 8. November 2005 enthält sämtliche der geforderten inhaltlichen Elemente. Zudem werden die verpflichteten Mieter in Dispositiv Ziffer III.2 einzeln und namentlich genannt. Die Aufforderung zur Beendigung der sexgewerblichen Nutzung der fraglichen Räume ist ferner in einem allgemeinverständlichen Sprachstil gehalten. Die Schlussfolgerung der Vorinstanz, es liege eine korrekte Rechtsmittelbelehrung vor, hält somit vor Art. 18 Abs. 2 KV/ZH stand. Demnach verstösst auch nicht ihr Schluss gegen die Kantons- oder Bundesverfassung, es liege kein Verfahrensfehler vor, weshalb ein Revisionsgrund zu verneinen sei.
3.4 Insoweit die Beschwerdeführer verlangen, die Räumungsanordnung hätte ihnen gegenüber mittels einer separaten Verfügung erfolgen müssen, ist darauf nicht weiter einzugehen, da nicht gerügt wird, inwiefern diesbezüglich Recht verletzt worden sei. Aus demselben Grund ist auch nicht auf die Forderungen einzugehen, im Rahmen eines Gesamtentscheids hätten die Anordnungen gegenüber den Mietern vom Rest deutlich abgetrennt bzw. die Mieter hätten im Rubrum des Entscheids als Partei aufgeführt werden müssen.
3.5 Inwiefern die Grundsätze rechtsstaatlichen Handelns (<ref-law>), der Grundsatz von Treu und Glauben (<ref-law>) sowie die Ansprüche auf ein gerechtes Verfahren und auf rechtliches Gehör (Art. 29 Abs. 1 und 2 BV) im vorliegenden Fall noch wegen anderer, in den bisherigen Erwägungen nicht behandelter Aspekte verletzt seien, wird von den Beschwerdeführern nicht in einer den gesetzlichen Anforderungen genügenden Weise dargetan. Darauf ist deshalb nicht weiter einzutreten.
4. Die Beschwerde ist daher abzuweisen, soweit darauf eingetreten werden kann.
Dem Ausgang des vorliegenden Verfahrens entsprechend sind die Gerichtskosten den Beschwerdeführern aufzuerlegen (<ref-law>). Parteientschädigungen sind keine zuzusprechen (Art. 68 Abs. 1 und 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten werden kann.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt unter solidarischer Haftung je zu gleichen Teilen.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Bausektion der Stadt Zürich und dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 7. April 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Kappeler