Sachverhalt:
A. Das Gastwirtschaftsgesetz für die Stadt Chur vom 24. September 2000 (im Folgenden: GWC), in Kraft seit 1. April 2001, regelt die Öffnungszeiten der ihm unterstellten Betriebe wie folgt:
Art. 11 Grundsatz
Gastwirtschaftsbetriebe dürfen von 06.00 Uhr bis 24.00 Uhr geöffnet sein.
Art. 12 Ausnahmen
a) Verlängerung
1 Der Stadtrat kann auf spezielles Gesuch hin jedem Gastwirtschaftsbetrieb dauernd längere Öffnungszeiten bewilligen.
2 Die Stadtpolizei kann für einzelne Tage, Anlässe und Betriebe längere Öffnungszeiten bewilligen, wenn das Gesuch bis spätestens 24.00 Uhr vorliegt.
b) Auflagen
Die Bewilligung längerer Öffnungszeiten kann für einzelne oder gemeinsam für mehrere nahe beieinander liegende Betriebe von einem Konzept zur Aufrechterhaltung von Ruhe, Ordnung und Sicherheit abhängig gemacht und mit Auflagen verbunden werden.
c) Verkürzung
Sofern Nachtruhe, öffentliche Ordnung und Sicherheit oder berechtigte Interessen des Jugendschutzes es erfordern oder die Auflagen gemäss lit. b nicht erfüllt werden, können vom Stadtrat auch kürzere Öffnungszeiten als in Art. 11 vorgesehen festgelegt oder gewährte Verlängerungen wieder entzogen werden. Die Verkürzung ist auch für mehrere nahe beieinander liegende Betriebe, ganze Strassenzüge, Quartiere oder für Teilbereiche von Betrieben möglich.
Gemäss Art. 22 GWC kann der Stadtrat Ausführungsbestimmungen erlassen.
B. Nachdem die Stadt Chur bei der Verlängerung von Öffnungszeiten zunächst eine liberale Praxis verfolgte, beschloss der Stadtrat von Chur (Exekutive) am 10. Oktober 2006 mit Blick auf die in gewissen Stadtteilen als unbefriedigend empfundene Situation (Lärmbelastung der Anwohnerschaft, Verunreinigungen, Ausschreitungen durch Alkoholisierte, etc.) die "Bewilligung von dauernd längeren Öffnungszeiten" neu nach Massgabe eines Modells zu regeln, welches das Stadtgebiet in verschiedene Rayons einteilt. Im Einzelnen sollten die Öffnungszeiten wie folgt angepasst werden:
Rayon 1: Altstadt und Lindenquai (neu) inkl. übriges Wohngebiet
Sonntag bis Donnerstag 24.00 Uhr
Freitag/Samstag bis maximal 02.00 Uhr
Rayon 2: Welschdörfli (Obertor - St. Margrethenstrasse bis Seilerbahnweg)
Sonntag bis Donnerstag 02.00 Uhr
Freitag/Samstag bis maximal 03.00 Uhr
Rayon 3: Industriegebiet
Sonntag bis Donnerstag 02.00 Uhr
Freitag/Samstag bis maximal 04.00 Uhr
Diese Regelung wurde vom Verwaltungsgericht des Kantons Graubünden auf Rekurs hin mit Urteil vom 23. Februar 2007 (publ. in: PVG 2007 Nr. 7) rechtskräftig geschützt, vom Stadtrat Chur gestützt auf ein mit den Wirten ausgearbeitetes gemeinsames Konzept, dessen Ergebnisse er abwarten wollte, aber nicht in Kraft gesetzt.
C. Mit Beschluss vom 29. Oktober 2007 stellte der Stadtrat Chur fest, dass weitere Massnahmen für eine spürbare und nachhaltige Verbesserung der Situation in den Gebieten Welschdörfli und Lindenquai notwendig seien, wobei in erster Priorität eine Verkürzung der Öffnungszeiten umgesetzt werden müsse. Entsprechend legte er die maximal möglichen Öffnungszeiten der Gastwirtschaftsbetriebe und die Gebietseinteilung neu mit Wirkung ab 1. Januar 2008 wie folgt fest:
Gebiet: Altstadt/Lindenquai und übriges Wohngebiet
Sonntag bis Donnerstag: 24.00 Uhr
Freitag/Samstag: bis max. 01.00 Uhr
Gebiet: Welschdörfli und Industrie
Sonntag bis Donnerstag: bis max. 02.00 Uhr
Freitag/Samstag: bis max. 03.00 Uhr
D. X._ und Y._ sind Pächter bzw. Eigentümer des in der Nähe des Welschdörfli gelegenen Restaurants/Cabarets "A._" (Erotik-Betrieb). Das Lokal durfte nach eigener Darstellung mit "Bewilligung für dauernd längere Öffnungszeiten" bisher stets gleich geöffnet bleiben wie die Lokale im Welschdörfli, d.h. Sonntag- bis Donnerstagnacht bis 02.00 Uhr und Freitag- und Samstagnacht bis 06.00 Uhr.
X._ und Y._ erhoben gegen den Stadtratsbeschluss vom 29. Oktober 2007 Beschwerde beim Verwaltungsgericht des Kantons Graubünden, welches das Rechtsmittel mit Urteil vom 25. Februar 2008 abwies.
E. Mit Eingabe vom 23. Juni 2008 erheben X._ und Y._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das Urteil des Verwaltungsgerichts vom 25. Februar 2008 sei aufzuheben und die Öffnungszeiten des Restaurants/Cabarets "A._" seien an diejenigen des Welschdörfli anzupassen, d.h. Sonntag bis Donnerstag mit permanenter Bewilligung bis max. 02.00 Uhr und Freitag/Samstag bis max. 03.00 Uhr.
Der Stadtrat Chur schliesst auf Abweisung der Beschwerde, das Verwaltungsgericht des Kantons Graubünden auf Abweisung, soweit darauf einzutreten sei.
F. Dem von den Beschwerdeführern gestellten Gesuch um aufschiebende Wirkung wurde mit Verfügung des präsidierenden Mitglieds der II. öffentlich-rechtlichen Abteilung vom 22. Juli 2008 teilweise insofern entsprochen, als sie ihr Lokal mit Öffnungszeiten für den Rayon 1 gemäss dem Beschluss des Stadtrates Chur vom 10. Oktober 2006 (Sonntag bis Donnerstag bis 24 Uhr; Freitag- und Samstagnacht bis zwei Uhr früh) betreiben dürfen. Im Übrigen wurde das Gesuch abgewiesen.

Erwägungen:
1. 1.1 Streitgegenstand bildet die durch Stadtratsbeschluss angeordnete gebietsbezogene Verkürzung der maximal möglichen Öffnungszeiten der Gastwirtschaftsbetriebe mit "Bewilligung für dauernd längere Öffnungszeiten". Ob es sich bei dieser Regelung um einen Akt der Rechtsetzung, d.h. um einen Erlass, oder um eine Verfügung handelt, ist für die Eintretensfrage ohne Belang. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten steht in beiden Fällen offen (vgl. <ref-law>). Für Erlasse haben die Ausschlussgründe gemäss <ref-law> keine Geltung (vgl. Urteile 2C_561/2007 vom 6. November 2008, E. 1.1.1 und 2C_462/2007 vom 11. September 2007, E. 2.1), doch fällt die streitige Anordnung auch als Verfügung inhaltlich unter keinen dieser Gründe. Das angefochtene Urteil des Verwaltungsgerichts stellt einen letztinstanzlichen kantonalen Endentscheid dar (Art. 86 Abs. 1 lit. d, gegebenenfalls in Verbindung mit <ref-law> sowie <ref-law>), womit das Rechtsmittel der Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig ist.
1.2 Als Betreiber eines im vom Stadtratsbeschluss erfassten "übrigen Wohngebiet" gelegenen Nachtclubs, welche bislang von einer grosszügigeren (Ausnahme-)Regelung der Öffnungszeiten, wie sie im nahe gelegenen Welschdörfli zum Tragen kamen, profitieren konnten, sind die Beschwerdeführer durch den angefochtenen Entscheid besonders berührt und besitzen ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung. Sie sind gemäss <ref-law> zur Beschwerde legitimiert.
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG; vgl. <ref-ruling> E. 2.1 S. 245 f.), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254; <ref-ruling> E. 1.4 S. 287).
1.4 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Die Beschwerdeführer rügen einen Verstoss gegen das Gebot von Treu und Glauben. Mit Beschluss des Stadtrates von Chur vom 5. Februar 2002, mit welchem dieser die Erteilung der Gastwirtschaftsbewilligung zur Führung des Restaurants/Cabarets "A._" zugesichert habe, sei verfügt worden, dass die dauernd verlängerten Öffnungszeiten an diejenigen im Gebiet des Welschdörfli angepasst werden könnten. In der Folge seien dem Lokal denn auch stets diese längeren Öffnungszeiten bewilligt worden. Es sei treuwidrig, wenn nunmehr nach gut sechs Jahren von den Betrieben im Welschdörfli abweichende, verkürzte Öffnungszeiten gelten würden. Die Beschwerdeführer hätten darauf vertrauen dürfen, ihr Lokal für einen langen Zeitraum entsprechend führen zu können.
2.2 Der in <ref-law> verankerte Grundsatz von Treu und Glauben verleiht einer Person Anspruch auf Schutz des berechtigten Vertrauens in behördliche Zusicherungen oder sonstiges, bestimmte Erwartungen begründendes Verhalten der Behörden, sofern sich dieses auf eine konkrete, den betreffenden Bürger berührende Angelegenheit bezieht. Der entsprechende Schutz entfällt in der Regel bei Änderung von Erlassen (statt vieler: <ref-ruling> E. 8.1 S. 60 mit Hinweisen). Der den Betrieb der Beschwerdeführer betreffende Beschluss des Stadtrates vom 5. Februar 2002 stellte insofern eine Zusicherung dar, als darin die Erteilung der Gastwirtschaftsbewilligung nach erfolgreicher Abnahme des Betriebes durch die Verwaltungspolizei in Aussicht gestellt wurde. Auch durften die Beschwerdeführer davon ausgehen, dass die in der Folge separat auszustellende, periodisch zu erneuernde Bewilligung für dauernd verlängerte Öffnungszeiten anlässlich ihrer erstmaligen Erteilung die gleichen zeitlichen Rahmenbedingungen enthalten würde, wie sie (damals) für das Welschdörfli vorgesehen waren. Eine dahingehende Erklärung, dass dies darüber hinaus und unabhängig von der jeweiligen Rechtslage auch für alle künftigen derartigen Bewilligungen gelten sollte, lässt sich dem Beschluss hingegen nicht entnehmen. Auch vermochte die anschliessende mehrmalige Verlängerung der Bewilligung zu den gleich günstigen Konditionen für sich allein keine verfassungsrechtlich geschützte Vertrauensposition zu begründen. Dass die Bewilligungen jeweils nur auf ein Jahr erteilt wurden, verschaffte der Behörde für deren Erneuerungen zwar keine völlige Freiheit; ein zugelassener Betrieb muss sich auf eine gewisse Beständigkeit der gewährten Bedingungen verlassen können. Als für die Ausführungsvorschriften zuständiges Rechtsetzungsorgan war der Stadtrat aber befugt, generelle Änderungen der maximal zulässigen Öffnungszeiten zu beschliessen. Dies muss umso mehr gelten, wenn - worauf noch näher einzugehen sein wird (unten E. 3.4) - zwischenzeitlich eine im vorliegenden Zusammenhang relevante Zonenplanänderung verabschiedet wurde.
3. 3.1 Die Beschwerdeführer wenden sich nicht gegen die im streitigen Stadtratsbeschluss vorgesehene Verkürzung der Öffnungszeiten im Allgemeinen. Sie kritisieren einzig die beabsichtigte Zuordnung ihres Betriebes zum Rayon "übriges Wohngebiet" und bringen vor, indem die Stadt Chur ihren Nachtclub bei den Öffnungszeiten anders behandle als die Lokale im Welschdörfli und insbesondere die in unmittelbarer Nähe gelegenen Konkurrenzbetriebe "G._" und "H._", verstosse sie gegen das Willkürverbot und das Rechtsgleichheitsgebot.
3.2 Die Kantone sind gemäss konstanter Rechtsprechung des Bundesgerichts befugt, aus Gründen der öffentlichen Ruhe und Ordnung bzw. insbesondere zum Schutz der Nacht- und Feiertagsruhe Vorschriften über die Ladenschlusszeiten (<ref-ruling> E. 2.3.1 S. 284; <ref-ruling> E. 2c S. 93; <ref-ruling> E. 2b/bb S. 379; <ref-ruling> E. 7a S. 486; <ref-ruling> E. 3 S. 400 f.; <ref-ruling> E. 3b/3c S. 503 f. sowie E. 5b S. 507) und - für den Bereich des Gastwirtschaftsgewerbes - über die Polizeistunde bzw. die möglichen Ausnahmen hievon zu erlassen (<ref-ruling> E. 4c S. 49; Urteile 2P.340/1993 vom 14. September 1995, E. 3f/aa; 2P.371/1993 vom 14. Juli 1995, E. 3a). Dem kantonalen (oder kommunalen) Gesetzgeber steht bei der Festlegung der Schliessungszeiten wie auch bei der Statuierung allfälliger Sonderregelungen für einzelne Bereiche ein weiter Gestaltungsspielraum zu, den der Verfassungsrichter zu respektieren hat, solange die einschlägigen grundrechtlichen Schranken, d.h. insbesondere das Willkürverbot und das Gleichbehandlungsgebot, gewahrt bleiben (vgl. <ref-ruling> E. 4 S. 435 ff.).
Soweit es um die Würdigung örtlicher Verhältnisse geht, welche die kantonalen Instanzen besser kennen, und soweit sich ausgesprochene Ermessensfragen stellen, übt das Bundesgericht bei der Überprüfung Zurückhaltung (<ref-ruling> E. 3d S. 284; <ref-ruling> E. 2b S. 265, je mit Hinweisen).
3.3 Vorauszuschicken ist, dass den Gemeinden in städteplanerischer Hinsicht ein grosser Ermessensspielraum zukommt. Insbesondere mit Blick auf die Lärmimmissionen lässt es sich sachlich rechtfertigen, die nächtlichen Vergnügungsangebote in einem bestimmten Perimeter zu konzentrieren, um so Quartiere mit überwiegendem Wohnanteil vor den negativen Auswirkungen des Nachtlebens zu schützen. Insofern erscheint es ohne weiteres vertretbar, wenn die Stadt Chur bloss Gastwirtschaftsbetriebe im historisch gewachsenen Vergnügungsviertel (Welschdörfli), wo sich bereits eine Vielzahl solcher Lokale befinden, sowie im kaum bewohnten Industriequartier in den Genuss grosszügigerer Ausnahmebewilligungen hinsichtlich ihrer Öffnungszeiten kommen lässt.
Nach den verbindlichen Feststellungen im angefochtenen Urteil, welche die Beschwerdeführer nicht zu entkräften vermögen, steht aufgrund aktenkundiger Polizeiberichte fest, dass es bei ihrem Lokal zu Störungen der Nachtruhe gekommen ist. Der Einwand der Beschwerdeführer, dass die betreffenden Lärmimmissionen in erster Linie auf einen nahe gelegenen grossen öffentlichen Parkplatz zurückzuführen seien, wird vor Bundesgericht erstmals vorgebracht und ist damit nicht zu hören (oben E. 1.4). Nicht zu beanstanden ist jedenfalls die Annahme der Vorinstanz, dass das Lokal der Beschwerdeführer aufgrund der verlängerten Öffnungszeiten einen Anziehungspunkt für "Nachtschwärmer" bildet und damit auch selber zur erwähnten Nachtlärmproblematik beiträgt. Wenn die Stadt Chur unter den gegebenen Umständen Ausnahmen von den gemäss Gastwirtschaftsgesetz geltenden Öffnungszeiten nur noch in restriktiverem Umfang gestatten will, erscheint dies als taugliches Mittel, um die Einhaltung der Nachtruhe im betreffenden Gebiet zu verbessern.
3.4 Nicht zu beanstanden ist auch die ungleiche Behandlung der Konkurrenzbetriebe im Welschdörfli gegenüber dem unweit von diesen, jedoch ausserhalb des betreffenden Rayons gelegenen Nachtclub der Beschwerdeführer. Nach den Feststellungen im angefochtenen Entscheid findet in unmittelbarer Umgebung des Restaurants/Cabarets "A._" eine intensive Wohnbautätigkeit mit rund 130 neuen Miet- und Eigentumswohnungen statt. Die im Welschdörfli gelegenen Konkurrenzbetriebe ständen demgegenüber in einer deutlich grösseren Entfernung zu den erwähnten Wohnüberbauungen. Diese Feststellung kritisieren die Beschwerdeführer als willkürlich: Ihr Betrieb sei genau 32,8 m vom Eingang der neuen Wohnbaute entfernt, wogegen die Distanz zwischen Letzterer und dem Konkurrenzbetrieb "H._" 37,2 m betrage; von einer "deutlich grösseren Entfernung" könne insofern nicht gesprochen werden. Auch sei gegenüber dem "G._" ein in früheren Jahren erstelltes Wohn- und Gewerbehaus im Abstand von 29,1 m gelegen. Wie es sich damit im Einzelnen verhält, kann dahingestellt bleiben, da die exakten räumlichen Dimensionen vorliegend nicht entscheidwesentlich sind (oben E. 1.4). Entsprechend ist auch auf eine Durchführung des beantragten Augenscheins durch das Bundesgericht zu verzichten. Ins Gewicht fällt nämlich vielmehr, dass sich die Stadt Chur für die vorgenommene Abgrenzung der Rayons auf die Vorgaben der Zonenplanung stützen konnte, welche für die Zone der genannten, innerhalb des Welschdörfli gelegenen Konkurrenzbetriebe (Zentrumszone ZA1) eine niedrigere Empfindlichkeitsstufe (ES III) vorsieht als für das Gebiet, in welchem der Nachtclub der Beschwerdeführer liegt. Dieses war vormals der Gemischten Zone zugeordnet und befindet sich seit einer Stadtplanungsrevision im Jahre 2006 in der Wohnzone W5 (mit einer Lärmempfindlichkeitsstufe ES II). Die Beschwerdeführer bestreiten im Übrigen nicht, dass die Umgebung ihres (von der Stadt als nunmehr zonenwidrig erachteten) Lokals - wie das Verwaltungsgericht festhält - zudem auch tatsächlich in erheblich grösserem Umfang als Wohngebiet genutzt wird als das Welschdörfli. Wenn die Stadt den Nachtclub der Beschwerdeführer mithin nicht von den (noch) grosszügigeren Öffnungszeiten, wie sie der streitige Stadtratsbeschluss für das Gebiet des Welschdörfli vorsieht, profitieren lassen will, sondern ihn den für das übrige Wohngebiet (sowie die Altstadt und den Lindenquai) geltenden, maximal möglichen Betriebszeiten unterstellt, erscheint dies durch sachliche Gründe gerechtfertigt und verfassungsrechtlich nicht zu beanstanden. Ein Verstoss gegen das Rechtsgleichheitsgebot oder das Willkürverbot liegt nicht vor.
4. Nach dem Gesagten ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unbegründet abzuweisen.
Entsprechend dem Ausgang sind die Kosten des bundesgerichtlichen Verfahrens den Beschwerdeführern unter solidarischer Haftung aufzuerlegen (<ref-law>). Parteientschädigungen sind nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, dem Stadtrat von Chur und dem Verwaltungsgericht des Kantons Graubünden, 1. Kammer, schriftlich mitgeteilt.
Lausanne, 20. Februar 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Moser