Sachverhalt:
A. Am 30. November 2008 nahmen die Stimmbürger des Kantons Zürich die Initiative "Ja zur Wahlfreiheit beim Medikamentenbezug (Zürcher Medikamentenabgabe-Initiative)" mit 54 % Ja- und 46 % Neinstimmen an. Am 9. Dezember 2008 ordnete der Regierungsrat des Kantons Zürich die Veröffentlichung der Ergebnisse der Volksabstimmung im Amtsblatt des Kantons Zürich an. Dieser Beschluss wurde zusammen mit den Ergebnissen am 12. Dezember 2008 im Amtsblatt veröffentlicht.
B. Mit Eingabe vom 17. Dezember 2008 erhoben Ruth Saxer und Werner Wiesendanger Stimmrechtsrekurs an den Regierungsrat des Kantons Zürich. Sie beantragten, die Volksabstimmung sei für ungültig zu erklären und es sei eine neue Abstimmung anzusetzen. Sie rügten, die Stellungnahme des Regierungsrats in der behördlichen Abstimmungszeitung sei unausgewogen und unvollständig gewesen; zudem sei der Titel der Initiative verkürzt wiedergegeben worden, ohne den klarstellenden Zusatz "Zürcher Medikamentenabgabe-Initiative". Weiter machten sie geltend, der Ausgang der Abstimmung sei durch eine massive Falschpropaganda der Ärzteschaft beeinflusst worden; die zuständigen Behörden hätten es versäumt, diese Falschpropaganda richtig zu stellen.
Der Regierungsrat erachtete den Rekurs als verspätet und trat darauf mit Beschluss vom 14. Januar 2009 nicht ein.
C. Dagegen haben Ruth Saxer und Werner Wiesendanger am 19. Februar 2009 Stimmrechtsbeschwerde ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und der Regierungsrat sei anzuweisen, auf ihren Stimmrechtsrekurs vom 17. Dezember 2008 einzutreten. Eventualiter sei der Stimmrechtsrekurs bzw. die Stimmrechtsbeschwerde vom Bundesgericht direkt zu beurteilen, die Volksabstimmung vom 30. November 2008 über die Volksinitiative "Ja zur Wahlfreiheit beim Medikamentenbezug (Zürcher Medikamentenabgabe-Initiative)" für ungültig zu erklären und eine neue Volksabstimmung anzusetzen.
D. Die Direktion der Justiz und des Innern des Kantons Zürich beantragt namens des Regierungsrats, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Der Kantonsrat hat auf eine Vernehmlassung verzichtet.

Erwägungen:
1. Die Beschwerdeführer rügen, der Regierungsrat sei zu Unrecht auf ihren Stimmrechtsrekurs nicht eingetreten und habe dadurch ihre politischen Rechte verletzt. Diese Rüge kann mit Stimmrechtsbeschwerde i.S.v. Art. 82 lit. c BGG geltend gemacht werden (in <ref-ruling> nicht veröffentlichte E. 1a; Urteil 1C_208/2008 vom 3. Dezember 2008 E. 1). Zur Beschwerde ist gemäss Art. 89 Abs. 3 BGG legitimiert, wer in der betreffenden Angelegenheit stimmberechtigt ist. Dieses Erfordernis erfüllen die Beschwerdeführer. Fraglich ist dagegen, ob der angefochtene Entscheid kantonal letztinstanzlich ist (Art. 88 Abs. 1 lit. a BGG), oder ob er noch ans Zürcher Verwaltungsgericht hätte weitergezogen werden können.
2. Das Zürcher Verwaltungsgericht beurteilt Beschwerden gegen letztinstanzliche Anordnungen von Verwaltungsbehörden (§ 41 Abs. 1 des Zürcher Verwaltungsrechtspflegegesetzes vom 24. Mai 1959 [VRG]). Dazu gehören insbesondere auch Rekursentscheide des Regierungsrats (KÖLZ/BOSSHART/RÖHL, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Aufl., § 41 N 28). Gemäss § 43 Abs. 1 lit. a VRG ist die Beschwerde unzulässig gegen Anordnungen auf dem Gebiet von Wahlen und Abstimmungen; Abs. 2 dieser Bestimmung sieht jedoch vor, dass die Beschwerde auch in den Fällen von Abs. 1 zulässig ist, soweit die Verwaltungsgerichtsbeschwerde an das Bundesgericht offensteht.
Gemäss § 5 der Verordnung des Regierungsrats des Kantons Zürich vom 29. November 2006 über die Anpassung des kantonalen Rechts an das Bundesgerichtsgesetz (VO BGG, OS 61, 480) ist unter der Verwaltungsgerichtsbeschwerde die ordentliche Beschwerde an das Bundesgericht zu verstehen. Zur ordentlichen Beschwerde in öffentlich-rechtlichen Angelegenheiten gehört auch die Stimmrechtsbeschwerde nach Art. 82 lit. c BGG. Insofern steht die Beschwerde an das Verwaltungsgericht auch gegen Anordnungen auf dem Gebiet von Wahlen und Abstimmungen offen (<ref-ruling> E. 1.2.2 S. 202).
2.1 Mit dem Erlass von § 5 VO BGG, der sich auf Art. 130 Abs. 4 BGG stützt, ist der Kanton Zürich seiner Verpflichtung gemäss Art. 88 Abs. 2 Satz 1 BGG nachgekommen, ein Rechtsmittel gegen behördliche Akte vorzusehen, welche die politischen Rechte verletzen können. Vor dem Hintergrund von Art. 29a BV und der Zielsetzungen des Bundesgerichtsgesetzes hat das Bundesgericht entschieden, dass die Kantone als Rechtsmittelinstanz im Sinne von Art. 88 Abs. 2 Satz 1 BGG eine gerichtliche Behörde einsetzen müssen (<ref-ruling> E. 1.2 S. 201; Urteil des Bundesgerichts 1P.338 und 582/2006 vom 12. Februar 2007 E. 3.10, publ. in: ZBl 108/2007 S. 313).
Die Übergangsfrist gemäss Art. 130 Abs. 3 BGG für den Erlass der entsprechenden Ausführungsbestimmungen ist am 1. Januar 2009 abgelaufen. Der angefochtene Entscheid wurde am 14. Januar 2009 und damit nach Ablauf dieser Übergangsfrist erlassen. Auf solche Entscheide findet § 5 VO BGG jedenfalls Anwendung (Entscheid 1C_183/2008 vom 23. Mai 2008 E. 1.1.5; zur Anwendbarkeit von § 5 VO BGG vor Ablauf der Übergangsfrist vgl. <ref-ruling> E. 2.4 S. 13; <ref-ruling> E. 1.2.1 S. 202; Urteil 1C_183/2008 vom 23. Mai 2008 E. 1.1.3).
Allerdings nimmt Artikel 88 Abs. 2 Satz 2 BGG Akte des Parlaments und der Regierung ausdrücklich aus; für diese besteht daher keine Verpflichtung der Kantone, einen kantonalen Rechtsmittelzug einzurichten. Fraglich ist deshalb, ob der Regierungsrat gestützt auf Art. 130 Abs. 4 BGG befugt war, auch Rechtsstreitigkeiten betreffend einen Akt der Regierung per Verordnung dem Verwaltungsgericht zuzuweisen, in Abweichung von Art. 43 Abs. 1 lit. a VRG.
2.2 Zunächst ist zu prüfen, ob der vorliegende Rechtsstreit überhaupt einen Akt der Regierung betrifft.
2.2.1 Gegenstand der Beschwerde vor Bundesgericht ist ein Nichteintretensentscheid des Regierungsrates. Rekursentscheide des Regierungsrats sind grundsätzlich keine Akte der Regierung i.S.v. Art. 88 Abs. 2 Satz 2 BGG, sondern unterliegen der allgemeinen Regelung, wonach letztinstanzlich ein kantonales Gericht zuständig sein muss (<ref-ruling> E. 1.2.2 S. 202). Fraglich kann allerdings sein, ob dies auch dann gilt, wenn der Regierungsrat in seinem Rekursentscheid nicht über den Akt einer untergeordneten (kommunalen oder kantonalen) Behörde entscheidet, sondern (wie bei einer Einsprache oder einem Wiedererwägungsbegehren) über einen Akt des Regierungsrats selbst. Dies wird erwogen von GEROLD STEINMANN, (Basler-Kommentar, Art. 88 Rz. 12 und 13); das Bundesgericht hat diese Frage noch nicht entschieden.
2.2.2 Der Stimmrechtsrekurs der Beschwerdeführer richtete sich u.a. gegen die Stellungnahme des Regierungsrats in der behördlichen Abstimmungszeitung; sodann wurde den zuständigen Behörden und damit auch dem Regierungsrat vorgeworfen, sie hätten es unterlassen, private Falschpropaganda richtigzustellen. Damit betraf der Rekurs (zumindest auch) Handlungen und Unterlassungen der Regierung im Vorfeld der Abstimmung.
Zu den Akten der Regierung i.S.v. Art. 88 Abs. 2 Satz 2 BGG zählen nicht nur Entscheide und Erlasse, sondern auch Realakte im Zusammenhang mit Wahlen und Abstimmungen (Regina Kiener, Beschwerde in öffentlich-rechtlichen Angelegenheiten, in: Tschannen (Hrsg.), Neue Bundesrechtspflege, Bern 2007, S. 250 oben), namentlich Abstimmungserläuterungen und -informationen (Steinmann, a.a.O., Art. 88 N. 13; Thomas Pfisterer, Der kantonale Gesetzgeber vor der Reform der Bundesrechtspflege, in: Ehrenzeller/Schweizer, Die Reorganisation der Bundesrechtspflege - Neuerungen und Auswirkungen in der Praxis, St. Gallen 2006, S. 306; vgl. auch Hansjörg Seiler/Nicolas von Werdt/Andreas Güngerich, Bundesgerichtsgesetz, Art. 88 N. 11: Interventionen der Regierung in den Abstimmungskampf).
Fraglich erscheint dagegen, ob auch ein Akt der Regierung i.S. dieser Bestimmung vorliegt, soweit die Beschwerdeführer die Beeinflussung der Abstimmung durch private Falschpropaganda geltend machen und in diesem Zusammenhang pauschal "den zuständigen Behörden" vorwerfen, sie hätten einschreiten und die Falschinformationen richtigstellen müssen (zur Schwierigkeit der Zurechnung von behördlichen Informationen vgl. Michel Besson, Der Schutz der politischen Rechte auf Bundesebene, FS-Heinrich Koller, 2006, S. 230 ff.; derselbe, Die Beschwerde in Stimmrechtssachen, in: Ehrenzeller/Schweizer, Die Reorganisation der Bundesrechtspflege - Neuerungen und Auswirkungen in der Praxis, St. Gallen 2006, S. 426 ff.).
2.3 Die Qualifikation als Regierungsakt kann allerdings offen bleiben, wenn der Regierungsrat befugt war, in seiner Übergangsregelung sämtliche Stimmrechtsbeschwerden dem Verwaltungsgericht zuzuweisen, auch soweit sie Akte der Regierung i.S.v. Art. 88 Abs. 2 Satz 2 BGG betreffen.
Bisher traf das Zürcher Recht in Stimmrechtssachen keine Unterscheidung danach, ob Akte der Regierung oder untergeordneter Behörden angefochten wurden. Mit Stimmrechtsrekurs konnten alle Handlungen und Unterlassungen von staatlichen Organen angefochten werden (Art. 147 Abs. 2 des Gesetzes über die politischen Rechte des Kantons Zürich vom 1. September 2003 [GPR]); zuständig waren der Bezirksrat (für kommunale Stimmrechtsangelegenheiten), der Kantonsrat (betreffend die Wahl des Kantonsrats) und im Übrigen der Regierungsrat (§ 149 GPR). Die Beschwerde ans Verwaltungsgericht war in jedem Fall ausgeschlossen (§ 43 Abs. 1 lit. a VRG).
Diese Rechtsmittelordnung, die keinen gerichtlichen Rechtsschutz in Stimmrechtsangelegenheiten vorsah, wurde mit Ablauf der Übergangsfrist gemäss Art. 130 Abs. 3 BGG bundesrechtswidrig (vgl. oben E. 2.1). Der Regierungsrat war daher befugt, gestützt auf Art. 130 Abs. 4 BGG eine bundesrechtskonforme Übergangsregelung zu erlassen (<ref-ruling> E. 2.4 S. 12 f.). Dabei durfte er an die bisherige Systematik anknüpfen und eine generelle Übergangslösung für alle Anordnungen auf dem Gebiet der Wahlen und Abstimmungen erlassen. Er war somit nicht verpflichtet, erstinstanzliche Akte der Regierung von der Übergangslösung auszunehmen und damit Differenzierungen vorzunehmen, die dem geltenden Zürcher Recht fremd sind und zu Rechtsunsicherheit führen können.
Es wird Sache des Gesetzgebers sein, ob er von der Möglichkeit gemäss Art. 88 Abs. 2 Satz 2 BGG Gebrauch machen will, (alle oder gewisse) Akte der Regierung und/oder des Parlaments nicht der kantonalen Gerichtsbarkeit zu unterstellen, unter Inkaufnahme der damit verbundenen Nachteile (Gabelung des Rechtswegs; schwierige Abgrenzungsfragen).
3. Nach dem Gesagten ist mangels Letztinstanzlichkeit auf die Beschwerde nicht einzutreten (vgl. Botschaft des Bundesrats vom 28. Februar 2001 zur Totalrevision des Bundesrechtspflege, BBl 2001 S. 4290 zu Art. 27 Abs. 2 E-BGG; Markus Boog, Basler Kommentar zum BGG, Art. 30 N. 3; Seiler/v. Werdt/Güngerich, Art. 30 N. 2). Diese ist dem Zürcher Verwaltungsgericht zur Behandlung zu überweisen.
Da der angefochtene Entscheid eine falsche Rechtsmittelbelehrung enthält und die Beschwerdeführer (bzw. ihr Rechtsvertreter) dies nicht ohne Weiteres erkennen konnten, darf ihnen daraus kein Nachteil erwachsen (Art. 49 BGG). Es werden daher keine Gerichtskosten erhoben (Art. 66 Abs. 1 und 4 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Die Eingabe der Beschwerdeführer vom 19. Februar 2009 wird dem Verwaltungsgericht des Kantons Zürich zur Behandlung überwiesen.
3. Es werden keine Gerichtskosten erhoben.
4. Dieses Urteil wird den Beschwerdeführern, dem Regierungsrat und dem Verwaltungsgericht des Kantons Zürich schriftlich mitgeteilt.
Lausanne, 29. Juni 2009
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Féraud Gerber