Sachverhalt:
A. Vom 14. Mai bis 14. Juni 2004 fand in der Stadt Chur die Mitwirkungsauflage zur Gesamtrevision der Stadtplanung statt. Zur öffentlichen Einsichtnahme lagen der Planungs- und Mitwirkungsbericht, die Zonenplan-Änderungen 1:5'000, der neue Zonenplan 2005 (1: 5'000), der Generelle Gestaltungsplan (GGP) 2005 (1:5'000), der Generelle Erschliessungsplan (GEP), Änderungen und Ergänzungen (1:5'000), der Generelle Erschliessungsplan 2005 (neu) 1:5'000, die Gefahrenzonenpläne (1:5'000 und Detailpläne), das Baugesetz 2005 (neu), die Ausführungsverordnung zum Baugesetz, die Parkplatzverordnung und das Reklamereglement auf. Private hatten gemäss Auflagetext die Möglichkeit, bis zum 14. Juni 2004 zur Gesamtrevision schriftlich Stellung zu nehmen. Organisationen, die in der Begleitkommission vertreten waren oder dies bis zum 14. Juni 2004 ankündigten, konnten ihre schriftliche Stellungnahme bis am 9. Juli 2004 einreichen. Am 26. November 2006 nahm die Stimmbevölkerung der Stadt Chur die Totalrevision der Stadtplanung an und verabschiedete sie zuhanden der regierungsrätlichen Genehmigung. Gegenstand des GEP bildet nebst anderem die sogenannte Langsamverkehrsplanung (Fuss- und Fahrradverkehr). Dazu legte die Stadt insbesondere Fuss-/Spazierwege fest, wobei sie zwischen "bestehenden" und "neuen/geplanten" Wegen unterschied. Einen solchen Fuss-/Spazierweg hat die Stadt u.a. im Wohngebiet Loë vorgesehen, um eine neue direkte und gerade Fussgängerverbindung ab der Sonnenbergstrasse in südlicher Richtung über die untere Florastrasse, die Falknisstrasse und die Fusswegparzelle Nr. 1667 bis zur Loëstrasse zu realisieren. Soweit diese neue Verbindung über die untere Florastrasse, die städtische Wegparzelle Nr. 3579, die Falknisstrasse, die Neubruchstrasse und die Wegparzelle Nr. 1667 führt, wurde sie als "bestehend" klassifiziert; im Bereich der Grenzen der Parzellen Nrn. 3378/3603 resp. 3606/244 bzw. 3580/3578 ist sie als "neu/geplant" im GEP verzeichnet. Zweck dieser Fuss- und Spazierwegfestlegung soll sein, den Leuten aus dem weitläufigen Wohnquartier zwischen Loëstrasse und Masanserstrasse eine zusätzliche horizontale Nord-Süd-Fusswegverbindung in Richtung Stadtzentrum zu gewährleisten. Andererseits sollen dadurch die einzelnen Teile des weitläufigen Wohngebietes besser untereinander verbunden werden (Erhöhung der Quartierdurchlässigkeit für Fussgänger). Diese neue Fussgängerverbindung zwischen der unteren Florastrasse, der Falknisstrasse, der Parzelle Nr. 1667 und der Loëstrasse wurde erst nach dem Mitwirkungsverfahren in den GEP aufgenommen. Die u.a. betroffenen Grundeigentümer Ehegatten X._ wurden darüber nach der Volksabstimmung, nämlich am 3. April 2007, von der Stadt in Kenntnis gesetzt.
B. Die Ehegatten X._ gelangten hierauf am 4. Mai 2007 mit Planungsbeschwerde an die Regierung, dies mit dem sinngemässen Begehren, die entsprechenden Festlegungen nicht zu genehmigen. Eventualiter stellten sie Antrag, es sei nur das Teilstück über die Wegparzelle Nr. 1667 nicht zu genehmigen. Subeventuell sei die Verbindung auf die Parzelle Nr. 251 zu verlegen. Subsubeventualiter sei die ganze Angelegenheit an die Stadt zur neuen Überarbeitung und Neuentscheidung zurückzuweisen, dies unter Wahrung der Mitwirkungsrechte der Bevölkerung. Die Beschwerdeführer bemängelten insbesondere in formeller Hinsicht, dass bezüglich der angefochtenen Wegfestlegung kein Mitwirkungsverfahren durchgeführt worden war: Der Weg hatte noch nicht Gegenstand des in die Mitwirkungsauflage gegebenen GEP gebildet und eine Neuauflage zur Mitwirkung war auch später nicht nachgeholt worden.
C. Die Regierung des Kantons Graubünden wies die Beschwerde am 22. Oktober 2007 ab, soweit sie darauf eintrat. Gleichzeitig genehmigte sie die im GEP 1:5'000 vom 26. November 2006 enthaltene Fuss-/Spazierwegfestlegung im Abschnitt zwischen der Sonnenbergstrasse und Neubruchstrasse (via untere Florastrasse-Falknisstrasse) samt Fortsetzung bis zur Loëstrasse über die Parzelle Nr. 1667. Die Regierung begründete diesen Entscheid im Wesentlichen damit, dass im Planungs- und Mitwirkungsbericht zur Gesamtrevision im Dezember 2006 nicht sämtliche Festlegungen hätten kommentiert werden müssen. Das öffentliche Interesse an der neu geplanten Wegverbindung ohne unnötige Umwege überwiege die privaten Interessen der Beschwerdeführer am Erhalt der Wegparzelle Nr. 1667 im letzten Teilabschnitt.
D. Dagegen gelangten die Beschwerdeführer an das Verwaltungsgericht des Kantons Graubünden. Sie argumentierten u.a., die Wegalternative über die unmittelbar im Osten anschliessende Parzelle Nr. 251 (im Eigentum des Kantons) stelle sehr wohl eine realistische und vernünftige Lösung dar. Nach Durchführung eines Augenscheins am 4. Mai 2008 wies das Verwaltungsgericht die Beschwerde am 27. Mai 2008 ab, soweit es darauf eintrat.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. Oktober 2008 beantragen die Ehegatten X._ dem Bundesgericht, das vorerwähnte Urteil des Verwaltungsgerichts aufzuheben. Das Teilstück über die Parzelle Nr. 1667 des am 26. November 2006 im Rahmen der Gesamtrevision der Stadtplanung beschlossenen "bestehenden/geplanten Fuss-/Spazierweg Sonnhaldenstrasse-Florastrasse-Falknisstrasse-Loëstrasse" im GEP 1:5'000 sei nicht zu genehmigen. Eventuell sei die Sache zur Neubeurteilung im Sinne der Erwägungen an die Vorinstanz oder die Stadt Chur zurückzuweisen.
Die Stadt Chur schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Desgleichen beantragt das kantonale Departement für Volkswirtschaft und Soziales namens der Regierung, die Beschwerde sei abzuweisen. Unter Hinweis auf die Ausführungen im angefochtenen Entscheid stellt auch das Verwaltungsgericht des Kantons Graubünden Antrag auf Abweisung der Beschwerde, soweit darauf einzutreten sei.
In ihrer Replik halten die Beschwerdeführer sinngemäss an ihren Begehren fest.
Erwägungen:
1. 1.1 Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Endentscheid (Art. 90 BGG). Gestützt auf Art. 82 lit. a BGG beurteilt das Bundesgericht Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält dazu keinen Ausschlussgrund. Gemäss Art. 34 Abs. 1 RPG in der Fassung nach Ziff. 64 des Anhangs zum Bundesgesetz vom 17. Juni 2005 über das Bundesverwaltungsgericht (VGG; SR 173.32; vgl. AS 2006 2261) gelten für die Rechtsmittel an die Bundesbehörden die allgemeinen Bestimmungen über die Bundesrechtspflege (BGE 133 II 249 E. 1.2 S. 251). Der umstrittene Genehmigungs- bzw. Beschwerdeentscheid der kantonalen Regierung betrifft einen Generellen Erschliessungsplan (GEP), der vor Bundesgericht den Regeln über die Anfechtung von Verfügungen im Sinne von Art. 82 lit. a BGG unterworfen ist ( vgl. BGE 133 II 353 E. 3.3 S. 358; vgl. BGE 117 Ia 302 E. 3 S. 305 f.; 116 Ia 207 E. 3b S. 211, je mit Hinweisen). Die Beschwerdeführer haben als Eigentümer der Parzelle Nr. 1667, über welche der streitbetroffene Fuss-/Spazierweg führen soll, ein schützenswertes Interesse an der Aufhebung des angefochtenen Verwaltungsgerichtsurteils und sind zur Beschwerde legitimiert. Auf die frist- und formgerecht eingereichte Beschwerde ist unter dem Vorbehalt der rechtsgenüglichen Begründung (E. 1.2 ff. hienach) einzutreten.
1.2 Nach Art. 42 Abs. 2 BGG ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Genügt die Beschwerdeschrift diesen Begründungsanforderungen nicht, so ist darauf nicht einzutreten. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (Art. 106 Abs. 1 BGG); dies setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die minimalen Begründungsanforderungen von Art. 42 Abs. 2 BGG erfüllt.
Strengere Anforderungen gelten, wenn - wie hier - die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung - BGE 133 II 249 E. 1.4.3 S. 255) geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG). Für derartige Rügen gelten die gleichen Begründungsanforderungen, wie sie gestützt auf Art. 90 Abs. 1 lit. b OG für die staatsrechtliche Beschwerde gegolten haben (BGE 133 II 249 E. 1.4.2 S. 254 mit Hinweisen). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen; auf rein appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (BGE 130 I 258 E. 1.3 S. 261 mit Hinweisen).
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Soweit ein Beschwerdeführer die vorinstanzlichen Sachverhaltsfeststellungen beanstandet und eine mangelhafte Sachverhaltsfeststellung für den Ausgang des Verfahrens entscheidend ist, kann er nur geltend machen, die Feststellungen seien offensichtlich unrichtig oder beruhten auf einer Rechtsverletzung im Sinne von Art. 95 BGG (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Eine entsprechende Rüge ist substanziiert vorzubringen (E. 1.2 hiervor). Vorbehalten bleibt die Sachverhaltsberichtigung von Amtes wegen nach Art. 105 Abs. 2 BGG (vgl. BGE 133 II 249 E. 1.4.3 S. 254 f.).
2. Die Beschwerdeführer rügen vorab, dass sich das Verwaltungsgericht mit ihrer Rüge, durch das Vorgehen der Stadt Chur in ihren Informations- und Mitwirkungsrechten verletzt worden zu sein, nicht auseinandergesetzt und damit Art. 29 Abs. 2 BV verletzt zu haben.
2.1 Die Begründungspflicht ist wesentlicher Bestandteil des Anspruchs auf rechtlichen Gehörs (Art. 29 Abs. 2 BV) und soll dem Betroffenen namentlich ermöglichen, einen Entscheid sachgerecht anzufechten. In der Begründung müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörden haben leiten lassen. Dabei kann sich die Begründung auf die für den Entscheid wesentlichen Gesichtspunkte beschränken (BGE 133 I 270 E. 34.1 S. 277).
Das Verwaltungsgericht nimmt zwar im angefochtenen Urteil nicht wörtlich Bezug auf den Umstand, dass das streitbetroffene Fusswegstück erst nach dem eigentlichen Mitwirkungsverfahren in den GEP aufgenommen worden ist und dazu keine zweite Anhörung der Bevölkerung stattgefunden hat. Dieser Sachverhalt war denn vor den kantonalen Instanzen auch unbestritten. Aus dem Gesamtzusammenhang des angefochtenen Entscheides ergibt sich sodann, dass das Verwaltungsgericht das Vorgehen der Stadt als rechtsgenüglich erachtet und darin keine Verletzung von Art. 4 RPG erblickt hat. So äussert es sich in E. 3a zum Vorwurf der ungenügenden Informations- und Abklärungspflicht der Stadt und erachtet diesen als nicht gerechtfertigt: Unter Verweis auf das Stadtentwicklungskonzept vom April 2003 und die dort generell formulierten Ziele hält es fest, dass dieses Grobkonzept allen Stadteinwohnern und somit auch den Beschwerdeführern zugestellt worden sei. In der Informationsbroschüre zur Volksabstimmung vom 26. November 2006 sei der GEP mit entsprechender Legende und Farbgebung abgedruckt, und schon dort sei eine durchgezogene Linie als künftig geplanter Fuss-/Spazierweg im Streckenabschnitt "Neubruch/Loë" auf der Wegparzelle Nr. 1667 der Beschwerdeführer eingezeichnet. Vom demokratisch angenommenen GEP 1:5'000 seien die Beschwerdeführer somit nicht überrumpelt oder falsch bzw. ungenügend informiert worden. Diese Ausführungen zeigen, dass sich das Verwaltungsgericht mit den Rügen der Beschwerdeführer zumindest summarisch auseinandergesetzt hat. Im Übrigen zeigen die Vorhalte der Beschwerdeführer, dass letztere durchaus in der Lage waren, diesen Punkt materiell zu rügen. In dieser Hinsicht ist dem Verwaltungsgericht folgerichtig keine Gehörsverletzung vorzuwerfen.
2.2 Gleiches gilt hinsichtlich des Vorwurfs, die Stadt Chur habe mit der Unterlassung der vorgängigen Information das rechtliche Gehör der Beschwerdeführer verletzt. Wenn das Verwaltungsgericht auch nicht weitergehende Erwägungen dazu angestellt hat, so geht aus seinem Urteil doch hervor, dass es diesen Vorhalt als unbegründet erachtet hat. Den Anspruch der Beschwerdeführer auf rechtliches Gehör hat es auch in diesem Punkt nicht verletzt.
3. Sodann machen die Beschwerdeführer geltend, das Verwaltungsgericht habe den Sachverhalt unvollständig festgestellt. Zum einen sei nicht festgehalten worden, dass der Fussweg über ihre Parzelle in der Mitwirkungsauflage nicht enthalten gewesen, sondern erst später in den GEP aufgenommen worden sei. Dass kein zweites Mitwirkungsverfahren durchgeführt worden sei, gehe aus dem Urteil ebenso wenig hervor wie die Tatsache, dass die Beschwerdeführer von der Stadt Chur über die Aufnahme des umstrittenen Planabschnitts in den GEP erstmals am 3. April 2007 - und damit nach dessen Annahme durch das Stimmvolk - informiert worden seien.
3.1 Wie bereits in E. 2.1 hiervor gesehen, ist diese Ausgangslage von den Entscheidinstanzen gar nie bestritten worden. Weder die Stadt Chur noch der Regierungsrat haben diese Tatsache in Abrede gestellt. Im Gegenteil, der Regierungsrat macht die entsprechenden Feststellungen in seinem Beschluss vom 22. Oktober 2007 in E. 2 und bezeichnet es als zutreffend, dass die angefochtene Wegfestlegung in der Mitwirkungsauflage nicht enthalten war. Das Verwaltungsgericht war nicht gehalten, darauf nochmals im Detail einzugehen. Mit seiner Auffassung, die Stadt sei ihren Informationsobliegenheiten u.a. mit der Zustellung der Abstimmungsbroschüre nachgekommen, nimmt es ganz offensichtlich auf diesen Sachverhalt Bezug, so dass es nicht schadet, wenn explizite Ausführungen dazu fehlen. Ein relevanter Mangel in der Sachverhaltsfeststellung liegt nicht vor.
3.2 Eine weitere offensichtlich unrichtige Sachverhaltsfeststellung durch das Verwaltungsgericht stellt nach Meinung der Beschwerdeführer dessen Verweis auf ein noch bevorstehendes, konkretes Baubewilligungsverfahren für den Fussweg dar. Das Verwaltungsgericht führt in E. 3c S. 11 aus, wo ganz genau die Abkürzung im letzten Teilstück (Neubruch-/Loëstrasse) schliesslich verlaufen werde (über die Parzelle Nr. 1667 oder teils auch über GB 152 [recte 251]), sei nicht Thema der nun zur Diskussion stehenden Planungsrevision, sondern müsse später noch Gegenstand eines konkreten Baubewilligungsverfahrens mit eigenständiger Anfechtungsmöglichkeit (nebst eines allfälligen Enteignungsverfahrens) sein. Die Beschwerdeführer wenden gegen diese Behauptung sinngemäss ein, aufgrund des GEP und der Vernehmlassung der Stadt Chur bestehe kein Zweifel daran, dass der Weg ausschliesslich über ihre Parzelle Nr. 1667 geführt werde.
Der Umstand, dass mit Blick auf die Parzelle der Beschwerdeführer auf einen bestehenden Weg zurückgegriffen werden kann, sprach für den Regierungsrat denn auch eindeutig für diese Variante, weshalb er das Subeventualbegehren, den Weg ausschliesslich auf die Parzelle Nr. 251 zu verlegen, abgewiesen hat. Den Beschwerdeführern ist darin zuzustimmen, dass nach dem Konzept des GEP die Linienführung über ihr Grundstück vorgegeben ist. Indes sieht Art. 45 Abs. 4 des kantonalen Raumplanungsgesetzes vom 6. Dezember 2004 (KRG/GR; BR 801.100) vor, dass bei der Projektierung geplanter Anlagen geringfügige Abweichungen gegenüber dem GEP zulässig sind, sofern die konzeptionellen Vorgaben gewahrt sind. Insofern sind die Ausführungen des Verwaltungsgerichts nicht falsch. Es hat denn auch keine gänzliche Verlegung des Wegs auf die Parzelle Nr. 251 in Betracht gezogen, sondern die Möglichkeit einer teilweisen Beanspruchung des Grundstücks Nr. 251 erwähnt. Von einer eventuellen gänzlichen Befreiung der Beschwerdeführer ist im angefochtenen Urteil nicht die Rede. Weitere Erwägungen hierzu erübrigen sich: Die etwaige Modifikation der Linienführung im weiteren Verlauf des Verfahrens betrifft nicht den heute rechtserheblichen Sachverhalt. Aufgrund der Aktenlage und der Feststellungen des Verwaltungsgerichts ist erstellt, dass die Parzelle der Beschwerdeführer (zumindest teils) von der vorgesehenen Linienführung betroffen ist. Die Rüge der Beschwerdeführer ist abzuweisen.
4. Die Beschwerdeführer rügen, dass sie über die nachträgliche Änderung des GEP erst nach der Volksabstimmung informiert worden sind. Aus ihrer Sicht hätte ein zweites Mitwirkungsverfahren durchgeführt werden müssen: Sie erblicken im Vorgehen der Behörden sowohl eine Verletzung von Art. 4 RPG als auch von Art. 29 Abs. 2 BV. Zwischen den beiden angerufenen Bestimmungen gilt es jedoch klar zu unterscheiden, da sie unterschiedliche Zielrichtungen verfolgen.
4.1 Art. 4 Abs. 1 RPG sieht vor, dass die mit Planungsaufgaben betrauten Behörden die Bevölkerung über Ziele und Ablauf der Planungen nach dem RPG unterrichten. Sie sorgen dafür, dass die Bevölkerung bei Planungen in geeigneter Weise mitwirken kann (Abs. 2). Den zuständigen Behörden steht bei der Anwendung von Art. 4 Abs. 2 RPG ein weiter Handlungsspielraum zu. Das gilt insbesondere auch für die Bestimmung des Kreises, welcher in ein Mitwirkungsverfahren einzubeziehen ist (BGE 133 II 120 E. 3.2 S. 124). Als Mindestgarantie fordert Art. 4 RPG, dass die Planungsbehörden neben der Freigabe der Entwürfe zur allgemeinen Ansichtsäusserung Vorschläge und Einwände nicht nur entgegennehmen, sondern auch materiell beantworten (BGE 111 Ia 164 E. 2d S. 168). Es genügt allerdings, wenn sich die Behörden materiell mit den Vorschlägen und Einwänden befassen, eine individuelle Beantwortung wird nicht verlangt (BERNHARD WALDMANN/PETER HÄNNI, Kommentar RPG, Bern 2006, Art. 4 N. 13; siehe auch Urteil 1C_101/2007 des Bundesgerichts vom 26. Februar 2008 E. 3.1).
4.1 Art. 4 Abs. 1 RPG sieht vor, dass die mit Planungsaufgaben betrauten Behörden die Bevölkerung über Ziele und Ablauf der Planungen nach dem RPG unterrichten. Sie sorgen dafür, dass die Bevölkerung bei Planungen in geeigneter Weise mitwirken kann (Abs. 2). Den zuständigen Behörden steht bei der Anwendung von Art. 4 Abs. 2 RPG ein weiter Handlungsspielraum zu. Das gilt insbesondere auch für die Bestimmung des Kreises, welcher in ein Mitwirkungsverfahren einzubeziehen ist (BGE 133 II 120 E. 3.2 S. 124). Als Mindestgarantie fordert Art. 4 RPG, dass die Planungsbehörden neben der Freigabe der Entwürfe zur allgemeinen Ansichtsäusserung Vorschläge und Einwände nicht nur entgegennehmen, sondern auch materiell beantworten (BGE 111 Ia 164 E. 2d S. 168). Es genügt allerdings, wenn sich die Behörden materiell mit den Vorschlägen und Einwänden befassen, eine individuelle Beantwortung wird nicht verlangt (BERNHARD WALDMANN/PETER HÄNNI, Kommentar RPG, Bern 2006, Art. 4 N. 13; siehe auch Urteil 1C_101/2007 des Bundesgerichts vom 26. Februar 2008 E. 3.1).
4.2 4.2.1 Der Kanton Graubünden hat diese bundesrechtlichen Vorgaben in Art. 13 der Raumplanungsverordnung vom 24. Mai 2005 (KRVO/GR; BR 801.110) mit der sogenannten "Mitwirkungsauflage" umgesetzt. Danach legt der Gemeindevorstand nach Abschluss des Vorprüfungsverfahrens den Entwurf für die neuen Vorschriften und Pläne zusammen mit dem Planungsbericht, einem allfälligen UVB und eventuellen Gesuchen für Zusatzbewilligungen in der Gemeinde während 30 Tagen öffentlich auf und gibt die Auflage im amtlichen Publikationsorgan der Gemeinde und im Kantonsamtsblatt bekannt (Abs. 1). Während der öffentlichen Auflage kann jedermann beim Gemeindevorstand Vorschläge und Einwendungen einbringen. Dieser prüft die Eingaben und nimmt dazu gegenüber den Mitwirkenden Stellung. Das Ergebnis des Mitwirkungsverfahrens wird zuhanden des beschlussfassenden Organs zusammengefasst (Abs. 2). Wird eine Vorlage nach der Mitwirkungsauflage geändert und erfolgt keine zweite Auflage, gibt der Gemeindevorstand die Änderung in der Publikation des Beschlusses über den Erlass oder die Änderung der Grundordnung bekannt und teilt diese ausserdem dem direkt Betroffenen schriftlich mit (Abs. 3).
Da das umstrittene Wegstück im Zeitpunkt der Mitwirkungsauflage noch nicht in der jetzigen Linienführung projektiert war, bestand für die Beschwerdeführer kein Anlass, entsprechende Anregungen und Vorschläge einzubringen. Der regierungsrätlichen Praxis entsprechend sah die Stadt Chur von einer zweiten Mitwirkungsauflage ab, da es sich bei der umstrittenen nachträglichen Änderung des Plans nicht um eine wesentliche Änderung handelte. Über die nachträgliche Änderung wurden die Beschwerdeführer, wie das Art. 13 Abs. 3 KRVO vorsieht, nach der Volksabstimmung informiert. Sie sind allerdings der Auffassung, dass die nachträgliche Änderung eine zweite Mitwirkungsauflage erheischt hätte. Dabei berufen sie sich sowohl auf Art. 13 KRVO (dazu nachfolgend E. 4.2.2) als auch 4 RPG (dazu nachfolgend E. 4.2.3).
4.2.2 Die Beschwerdeführer sind der Auffassung, Abs. 3 von Art. 13 KRVO/GR müsse restriktiv interpretiert werden und dürfe nur zur Anwendung gelangen, wenn die Planänderung aus einer Einwendung im Rahmen des Mitwirkungsverfahrens gemäss Abs. 2 resultiere, nicht aber, wenn die Planungsbehörde sie von sich aus vornehme. Aus dem Wortlaut von Art. 13 Abs. 3 KRVO/GR ergibt sich keine solche Einschränkung. Es ist jedenfalls nicht willkürlich, Art. 13 Abs. 3 KRVO dann anzuwenden, wenn eine Vorlage nachträglich geändert wird und keine zweite Auflage erfolgt, sei es, dass die Änderung auf einer in der Mitwirkungsauflage erfolgten Einwendung beruht, sei es, dass die Planungsbehörde von sich aus handelt. Im Übrigen erwähnt der sehr offen formulierte Art. 13 Abs. 3 KRVO nicht ausdrücklich, unter welchen Voraussetzungen eine zweite Auflage erfolgt.
4.2.3 Die Mitwirkung im Sinne von Art. 4 RPG stellt eine Einflussmöglichkeit dar, die von den Instrumenten der direkten Demokratie und des Rechtsschutzes zu unterscheiden ist. Sie gehört wie das Vernehmlassungsverfahren zu jenen institutionellen Formen, die keine rechtliche Bindung, sondern blosse politische Einflussnahme bewirken. Information und Mitwirkung ermöglichen die notwendige Breite der Interessenabwägung, bilden eine wichtige Grundlage für den sachgerechten Planungsentscheid und tragen damit zu einer qualitativ guten Planung bei. Deshalb verlangt deren Durchführung einen Zeitpunkt, in welchem die abschliessende Interessenabwägung noch offen ist (RUDOLF MUGGLI in: Kommentar zum RPG, Zürich 1999, Art. 4 N. 9; WALDMANN/HÄNNI, a.a.O., Art. 4 N. 1).
Berechtigt, sich informieren zu lassen und an der Mitwirkung teilzunehmen, ist "die Bevölkerung", damit weder nur die Stimmberechtigten der planenden Gebietskörperschaft noch nur die Grundeigentümer im Planperimeter oder die im Sinne der Rechtsschutzbestimmungen besonders betroffene Bevölkerung. Ein besonderer Interessennachweis ist nicht verlangt (Waldmann/Hänni, a.a.O., Art. 4 N. 9). Es liegt allerdings nahe, dass die durch die Planung direkt Betroffenen, welche in einem späteren Rechtsmittelverfahren zur Beschwerde legitimiert sind, ihre Interessen bereits im Mitwirkungsverfahren im Sinne von Einwendungen und Anregungen geltend machen (siehe auch Waldmann/Hänni, a.a.O., Art. 4 N. 2). Ob Art. 4 RPG im Falle gewichtiger (nachträglicher) Änderungen eine Wiederholung der Mitwirkungsauflage gebietet, braucht hier nicht abschliessend erörtert zu werden. Bundesrechtlich ist jedenfalls nicht zu beanstanden, wenn bei mit Blick auf den Gesamtzusammenhang untergeordneten nachträglichen Planänderungen ohne weitergehendes öffentliches Interesse von einer Nachholung des Mitwirkungsverfahrens abgesehen wird (so auch Muggli, a.a.O., Art. 4 N. 25 und Waldmann/Hänni, a.a.O., Art. 4 N. 114, mit Hinweis auf die Regelungen in Art. 58 Abs. 2 des Baugesetzes des Kantons Bern vom 9. Juni 1985 [BSG 721.0] oder in Art. 9 Abs. 3 der Genfer Loi d'application de la loi fédérale sur l'aménagement du territoire [LaLAT; RS/GE L 1 30]). Damit wird in Kauf genommen, dass Interessierte nicht vorgängig an jedem einzelnen Punkt der Neugestaltung teilnehmen können und namentlich von der Planänderung direkt Betroffene auf den Rechtsmittelweg verwiesen werden, wie das Art. 13 Abs. 3 KRVO vorsieht. Angesichts der Zweckbestimmung des Mitwirkungsrechts, welches höchstens indirekt dem Rechtsschutz dient, in erster Linie aber zur politischen Meinungsbildung einem breiten Personenkreis offen stehen soll, ist diese Praxis mit Art. 4 RPG vereinbar.
4.2.4 Bei der nachträglichen Aufnahme des umstrittenen Fusswegstückes in den GEP handelt es sich - entgegen der Meinung der Beschwerdeführer - um eine geringfügige Änderung des gesamten Erschliessungsplans, und es sind nur verhältnismässig Wenige davon direkt betroffen. Unter diesen Umständen war der Verzicht auf eine Wiederholung des Mitwirkungsverfahrens nicht bundesrechtswidrig. Mit ihrem Vorgehen haben die Behörden weder Art. 13 Abs. 3 KRVO/GR noch Art. 4 RPG verletzt.
5. Die Beschwerdeführer erblicken im Unterlassen der aus ihrer Sicht gebotenen vorgängigen Information über die Planänderung aber auch eine Verletzung ihres rechtlichen Gehörs.
5.1 Das rechtliche Gehör gemäss Art. 29 Abs. 2 BV dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheides dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheides zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (BGE 132 II 485 E. 3.2 S. 494; 127 I 54 E. 2b S. 56; 117 Ia 262 E. 4b S. 268, mit Hinweisen).
5.2 Es gibt eine Reihe von Kantonen, welche bereits die Planentwürfe auflegen und ein förmliches Einspracheverfahren vorsehen (§§ 9 und 16 des solothurnischen Planungs- und Baugesetzes vom 3. Dezember 1978 [PBG/SO; BGS 711.1]; § 24 Abs. 1 und 2 des aargauischen Baugesetzes vom 19. Januar 1993 [BauG/AG; SAR 713.100]; § 109 f. des basel-städtischen Bau- und Planungsgesetzes vom 17. November 1999 [BPG/BS; SG 730.100]). In andern Kantonen wiederum wird das Mitwirkungs- mit dem Planverfahren kombiniert (so etwa im Kanton Zürich, vgl. dazu WALTER HALLER/PETER KARLEN: Raumplanungs-, Bau- und Umweltrecht, Band I, 3. Auflage, Zürich 1999, Rn. 402 S. 112; § 24 Abs. 3 BauG/AG bei Sondernutzungsplanungen und bei Änderungen der Nutzungspläne und Nutzungsvorschriften von untergeordneter Bedeutung; Art. 43 al. 3 de la loi jurassienne sur les constructions et l'aménagement du territoire du 25 juin 1987 [LCAT/JU; RSJU 701.1]). Dagegen sieht der Kanton Graubünden für die Grundordnungsverfahren (Art. 12 ff. KRVO) kein eigentliches Einspracheverfahren vor, so dass sich die Beschwerdeführer hinsichtlich ihrer Einwendungen auf das Rechtsmittelverfahren verwiesen sahen (Art. 13 Abs. 3 KRVO).
Verschiedene Autoren halten dafür, dass die bloss nachträgliche Einräumung eines Rechtsmittels gegen einen bereits beschlossenen Nutzungsplan mit dem verfassungsrechtlichen Anspruch auf rechtliches Gehör nicht vereinbar sei, sondern der durch beabsichtigte Nutzungsplanungen in schutzwürdigen Interessen Betroffene die Möglichkeit haben müsse, bereits von Planentwürfen Kenntnis zu erhalten, sie einzusehen und dagegen Einwendungen zu erheben. Damit wird die Forderung erhoben, das rechtliche Gehör im Nutzungsplanverfahren vor der erstinstanzlichen Beschlussfassung zu gewähren (WALTER Haller, Das rechtliche Gehör bei der Festsetzung von Raumplänen, in: Festschrift für Otto K. Kaufmann zum 75. Geburtstag, Bern 1989, S. 376f.; weitere Hinweise bei Aemisegger/Haag, Kommentar zum Bundesgesetz über die Raumplanung, N. 11 Fn. 25). Für diese Auffassung könnte sprechen, dass die Gewährung des rechtlichen Gehörs im allgemeinen erheischt, dass Betroffene vor Erlass eines in ihre Rechtsstellung eingreifenden Entscheides durch die zuständige Behörde zum frühestmöglichen Zeitpunkt anzuhören sind. Es ist nicht zu übersehen, dass, wenn wie vorliegend Einwendungen gegen die Planänderung erst nach dem Beschluss über deren Erlass im anschliessenden Rechtsmittelverfahren vorgebracht werden können, deren Adressatin nicht die Planungsbehörde, sondern die Rechtsmittelinstanz ist. Dieser kommt zwar grundsätzlich umfassende Kognition zu (Art. 33 Abs. 3 lit. b RPG), doch respektiert sie das Planungsermessen der lokalen Planungesbehörde (BGE 127 II 238 E. 3b/aa S. 242 mit zahlreichen Verweisungen). Damit geht einher, dass die zur Stellungnahme zu den Einwendungen aufgerufene Planungsbehörde nach durchgeführter Abstimmung nicht mehr in dem Masse frei ist, wie sie es in einem der Abstimmung vorgelagerten Verfahren wäre, weshalb von ihr im Rahmen der Vernehmlassung im Rechtsmittelverfahren keine wirklich unvoreingenommene Prüfung zu erwarten ist, selbst wenn ein Rückkommen noch möglich wäre. Fraglich ist, ob das rechtliche Gehör der Betroffenen mit diesem Vorgehen hinreichend gewahrt wird.
5.3 Im Raumplanungsrecht werden individueller Rechtsschutz und damit die Gewährung des rechtlichen Gehörs in Art. 33 RPG abschliessend konkretisiert: Nutzungspläne werden öffentlich aufgelegt (Abs. 1). Das kantonale Recht sieht wenigstens ein Rechtsmittel vor (Abs. 2) und gewährleistet volle Überprüfung durch wenigstens eine Beschwerdebehörde (Abs. 3 lit. b). Damit erhalten die Legitimierten (Abs. 3 lit. a) Gelegenheit, im Beschwerdeverfahren mit ihren Anliegen zu den sie tangierenden Planänderungen gehört zu werden. Freilich ist es den Kantonen unbenommen, Planentwürfe nicht nur im Sinne der Mitwirkungsauflage, sondern auch zur Eröffnung eines dem individuellen Rechtsschutz dienenden Einspracheverfahrens für die direkt Betroffenen aufzulegen, stellt doch das Bundesrecht in Wahrung der kantonalen Hoheit nur Mindestvorschriften zur Gewährleistung des Rechtsschutzes auf (BGE 114 Ia 233 E. 2bc ff. S. 238 f.). Der in Art. 33 RPG konkretisierte Gehörsanspruch verlangt (nur), dass sich entweder die kommunale oder die kantonale Behörde im Einsprache-, Beschwerde- oder Homologationsverfahren mit den formgerecht und innert Frist erhobenen Einwendungen materiell befassen muss (BGE 107 Ia 273). Verlangt wird in Art. 33 RPG lediglich die Auflage der Nutzungspläne, nicht aber auch der Planentwürfe. Diesem Anspruch genügt ein Verfahren, das die öffentliche Auflage des Nutzungsplanes erst nach dessen Festsetzung durch das zuständige Organ zur Einleitung des Rechtsmittelverfahrens anordnet. Das kantonale Recht, dem das Bundesrecht Rechnung trägt, sieht denn auch vielfach eine Trennung des politischen Willensbildungsprozesses vom Rechtsmittelverfahren in dem Sinne vor, dass die im Dienste des Rechtsschutzes stehende Planauflage erst nach dem Entscheid des zuständigen Organs, in der Regel der Gemeindeversammlung als der Legislative der Gemeinde, erfolgt (BGE 114 Ia 233 E. 2cd S. 239 mit Hinweisen auf damalige kantonale Regelungen im Tessin, Basel-Landschaft und Zürich). Infolgedessen können Einwendungen im Rahmen eines Einsprache- oder Beschwerdeverfahrens vorgebracht werden (BGE 119 Ia 141 E. 5c/bb S. 150).
Dabei ist in Kauf zu nehmen, dass sich die Betroffenen je nach Ausgestaltung des kantonalen Verfahrens erst gegenüber der Rechtsmittelinstanz erstmalig rechtlich zur Wehr setzen können und nicht schon gegenüber der Planungsbehörde. Damit geht einher, dass die Rechtsmittelinstanz, die zwar über eine umfassende Sachverhalts- und Rechtskontrolle verfügt, das Planermessen der Planungsbehörde respektiert. Insoweit mag der Standard der Gehörsgewährung im Beschwerdeverfahren jenem der Gehörsgewährung im Einspracheverfahren nicht vollumfänglich zu entsprechen. Dennoch ist der Anspruch auf rechtliches Gehör gewahrt.
6. In materieller Hinsicht schliesslich erachten die Beschwerdeführer das Verhältnismässigkeitsprinzip als verletzt und bemängeln die Interessenabwägung des Verwaltungsgerichts.
6.1 Hinsichtlich des öffentlichen Interesses machen sie geltend, keine Planungsstudie habe je einen Fussweg über ihre Parzelle in Betracht gezogen. Vom umstrittenen Fussweg würden aus ihrer Sicht nur wenige Fussgänger profitieren, nämlich diejenigen, welche von der Falknis- oder Neubruchstrasse über die Loëstrasse in die Altstadt oder zum Coop-Einkaufszentrum gelangen möchten. Fussgänger in Richtung Bahnhof würden nach wie vor die Neubruchstrasse benützen. Seit jeher würden die Passanten Richtung Altstadt den nur 70 m längeren Weg über die Neubruchstrasse hinauf bis zur Loëstrasse benutzen. Das beidseitige Trottoir der Loëstrasse sei 4 m breit und gegen die Fahrbahn hin von Bäumen gesäumt. Dies entspreche insbesondere dem Sicherheitsbedürfnis von Kindern und älteren Leuten. Der einzige Vorteil der umstrittenen Variante bestehe in der Abkürzung um 70 m, wobei die Fussgänger auch in diesem Fall am Schluss auf die Loëstrasse gelangten. Der Behauptung der Behörden, der Fussweg werde dannzumal als Schulweg benützt, widersprechen die Beschwerdeführer. Die Schüler würden die Splügen- und die Neubruchstrasse benützen. Zudem befinde sich auf der kantonseigenen Parzelle Nr. 251 ein Parkplatz mit 45 Parkplätzen. Der neue Fussweg käme auf diese Autoeinfahrt und auf die Einfahrt zur Tiefgarage auf Parzelle Nr. 3402 zu stehen. Schliesslich befänden sich auch im Norden der Parzelle Nr. 1667 drei Parkplätze. Die umstrittene private Hauszugangsparzelle eigne sich darum aus Sicherheitsgründen nicht für einen Fussweg.
6.2 Was ihre tangierten privaten Interessen anbelangt, führen die Beschwerdeführer ins Feld, die Parzelle Nr. 1667 habe seit jeher einzig dem Zugang zum Mehrfamilienhaus auf der Parzelle Nr. 3402 gedient. Die Zugangsparzelle grenze unmittelbar an die Hausfassade an, weshalb Haus und Weg eine untrennbare Einheit bildeten. Beim Eingang an der Loëstrasse 25 weise der Weg eine Breite von lediglich 1.1 m auf. Zudem werde der Hauszugang als Abstellplatz für Fahrräder, Kinderwagen etc. genützt. Von der Wohnungstür gelangten die Hausbewohner direkt auf den Weg. Mit dessen öffentlicher Nutzung würden nebst Fussgängern auch Personen mit Kinderwagen, Hunden, Trottinetts, Rollbrettern und Velos darauf verkehren. Weil die Fenster im Parterre auf einer Höhe von 1.5 m lägen, böten sie Einblick in die Wohnungen. Damit werde die Privatsphäre der Mieter beeinträchtigt, namentlich nachts. Hinzu kämen Lärmimmissionen, einerseits tagsüber, insbesondere aber auch durch heimkehrende "Nachtschwärmer". Die nächtliche Beleuchtung des Wegs nennen die Beschwerdeführer als weitere Immission.
6.3 Art. 33 Abs. 2 RPG verlangt, dass das kantonale Recht wenigstens ein Rechtsmittel gegen Verfügungen und Nutzungspläne vorsieht, die sich auf dieses Gesetz und seine kantonalen und eidgenössischen Ausführungsbestimmungen stützen. Dabei ist eine volle Überprüfung durch wenigstens eine Beschwerdebehörde zu gewährleisten (Art. 33 Abs. 3 lit. b RPG). Volle Überprüfung bedeutet in diesem Zusammenhang nicht nur freie Prüfung des Sachverhalts und der sich stellenden Rechtsfragen, sondern auch eine Ermessenskontrolle. Die Beschwerdebehörde hat zu beurteilen, ob das Planungsermessen richtig und zweckmässig ausgeübt worden ist. Sie hat dabei allerdings im Auge zu behalten, dass sie Rechtsmittel- und nicht Planungsinstanz ist und daher nicht ihr eigenes Planungsermessen anstelle jenes der Planungsbehörde setzen darf. Die Überprüfung hat sich sachlich vor allem dort zurückzuhalten, wo es um lokale Angelegenheiten geht, hingegen so weit auszugreifen, dass die übergeordneten, vom Kanton zu sichernden Interessen einen angemessenen Platz erhalten. Im Rechtsmittelverfahren ist der den Planungsträgern durch Art. 2 Abs. 3 RPG zuerkannte Gestaltungsbereich stets zu beachten. Ein Planungsentscheid ist daher zu schützen, unabhängig davon, ob sich weitere, ebenso zweckmässige Lösungen erkennen lassen (vgl. BGE 127 II 238 E. 3b/aa S. 242 mit zahlreichen Verweisungen).
6.4 Das Verwaltungsgericht hat sich mit der Argumentation der Beschwerdeführer im angefochtenen Urteil - wenn auch nur summarisch - auseinandergesetzt. Es beanstandet nicht, dass die Vorinstanzen die neue Verbindung als den kürzesten, einfachsten und ungefährlichsten Weg für Fussgänger bezeichnet haben. Dazu zieht es in Erwägung, dass die am Augenschein alternativ vorgeschlagenen Wegrouten im Westen (via Masanserstrasse) und im Osten (Neubruchstrasse hoch bis zur Loëstrasse und von dort auf 4 m breitem Trottoir in Richtung Stadtzentrum) qualitativ und quantitativ der von der Stadt favorisierten Streckenführung kaum gleichgestellt oder als ebenbürtig bezeichnet werden könnten. Die Vorteile einer direkten und zusammenhängenden Wegverbindung (ohne unnötige Umwege von rund 100 m inkl. der Überwindung einer Höhendifferenz bis zum Ende der Neubruchstrasse und ohne gefährlichen und immissionsträchtigen Auto-/Motorradverkehr entlang der Masanserstrasse) für die schwächeren Verkehrsteilnehmer wie Schüler, Fussgänger mit Kinderwagen und ältere Menschen überwiegen nach Ansicht des Verwaltungsgerichts die privaten Interessen am uneingeschränkten Erhalt der persönlichen Ruhe und Ordnung sowie der Lärmfreiheit auf der Wegparzelle entlang der Hauseingänge. Die Partikularinteressen der Hausbewohner würden keinen höheren Schutz verdienen als das öffentliche Interesse an der Schaffung von gefahrlosen und einfachen Fusswegen selbst in städtisch dicht besiedelten Kerngebieten.
6.5 Mit Blick auf die in E. 6.3 zitierte Rechtsprechung ist die Interessenabwägung des Verwaltungsgerichts im Rahmen seiner Planüberprüfung nicht zu beanstanden, sondern erscheint nachvollziehbar. Selbst wenn andere Wegvarianten denkbar wären, erweist sich doch die kommunale Lösung nicht als rechtswidrig. Die Beschwerdeführer dringen mit ihrer Rüge zur angeblich mangelhaften Interessenabwägung nicht durch. Dass die vorgesehene Streckenführung unverhältnismässig wäre, ist nicht dargetan. Diesbezüglich hat das Verwaltungsgericht auch zum Vorschlag der Beschwerdeführer, den Weg ganz über die Parzelle Nr. 251 zu führen, Stellung genommen. Es hält dazu fest, dieses Grundstück sei bis heute auf der gesamten Nord-Süd-Ausdehnung durch massive Betonpflöcke samt Gitterdrahtzaun von der Parzelle Nr. 1667 räumlich getrennt. Eine Linienführung darüber hätte einen Abbruch derselben samt Aufhebung der dahinter gelegenen Bepflanzungen und Parkplätze zur Folge, dies alles, um eine Verschiebung des Wegs von 2-3 m nach Osten zu erreichen. Eine zumindest teilweise Verlegung des Fusswegs auf Parzelle Nr. 251 schliesst das Verwaltungsgericht unter Verweis auf das Baubewilligungsverfahren dennoch nicht aus. Dass dies mit Blick auf Art. 45 Abs. 4 KRG/GR möglich ist, wurde bereits aufgezeigt. Eine Verletzung des Verhältnismässigkeitsprinzips ist den kantonalen Behörden jedenfalls auch in dieser Hinsicht nicht vorzuwerfen.
Daraus ergibt sich, dass die Beschwerde abzuweisen ist. Bei diesem Verfahrensausgang haben die Beschwerdeführer die bundesgerichtlichen Kosten zu tragen (Art. 66 Abs. 1 BGG). Parteientschädigungen sind keine zuzusprechen (Art. 68 Abs. 3 BGG).
Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3. Parteientschädigungen werden keine zugesprochen.
4. Dieses Urteil wird den Beschwerdeführern, der Stadt Chur, der Regierung und dem Verwaltungsgericht des Kantons Graubünden, 4. Kammer, schriftlich mitgeteilt.
Lausanne, 16. Juni 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Scherrer