Sachverhalt:
A. Gestützt auf das Gesetz vom 18. Januar 1995 betreffend Einreihung und Entlöhnung der Mitarbeiterinnen und Mitarbeiter des Kantons Basel-Stadt (Lohngesetz) beschloss der Regierungsrat des Kantons Basel-Stadt am 11. Juli 1995 die "Überführung der Funktionen ins revidierte Lohngesetz und die Überführung der Mitarbeiterinnen und Mitarbeiter in die Lohnstufen". Dabei wurden auf den 1. Juli 1995 die Funktionen aller definitiv und provisorisch angestellten Mitarbeiter sowie die vakanten Soll-Stellen in Lohnklassen eingereiht.
Die im Ressort Dienste des Erziehungsdepartementes des Kantons Basel-Stadt beschäftigten Kleinklassenlehrkräfte mit Primarlehr- und heilpädagogischem Diplom wurden zum Teil in die Lohnklasse 16 (Regionale Tagesschulen und Waldschule Pfeffingen), zum Teil in die Lohnklasse 17 (Heilpädagogische Schule) überführt.
Gegen die Überführung in die Lohnklasse 16 wandten sich die Lehrkräfte der Regionalen Tagesschulen an den Regierungsrat des Kantons Basel-Stadt. Dessen abweisenden Entscheid fochten sie beim Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht an, welches ihren Rekurs am 8. September 2000 wegen unzulässiger Ungleichbehandlung gegenüber Lehrkräften mit gleichem Pflichtenheft teilweise guthiess.
In der Folge beschloss der Regierungsrat des Kantons Basel-Stadt am 3. Juli 2001, die Rekurrenten rückwirkend auf den 1. März 1996 in die Lohnklasse 17 einzureihen. Die übrigen Lehrkräfte des Ressorts Dienste des Erziehungsdepartementes mit gleichem Pflichtenheft, die sich nicht am Rechtsmittelverfahren beteiligt hatten, wurden ebenfalls in die Lohnklasse 17 eingereiht, dies indessen nicht rückwirkend, sondern mit Wirkung ab 1. August 2001.
B. A._, B._ und C._ sind Kleinklassenlehrkräfte der Waldschule X._, die dem Ressort Dienste des Erziehungsdepartementes angehört. Am 12. Februar 2002 verlangten sie vom Regierungsrat des Kantons Basel-Stadt, ihre Funktion ebenfalls rückwirkend (auf den 1. März 1996 bzw. das spätere Anstellungsdatum), d.h. nicht erst per 1. August 2001, in die Lohnklasse 17 einzureihen, was dieser am 6. August 2002 ablehnte. Dagegen wandten sich A._, B._ und C._ an das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht, das ihren Rekurs am 22. Oktober 2003 abwies.
C. Mit staatsrechtlicher Beschwerde vom 4. Februar 2004 beantragen A._, B._ und C._ dem Bundesgericht, das Urteil des Appellationsgerichts Basel-Stadt vom 22. Oktober 2003 aufzuheben.
Der Zentrale Personaldienst des Finanzdepartementes des Kantons Basel-Stadt stellt namens des Regierungsrates den Antrag, die Beschwerde abzuweisen.
Das Appellationsgericht Basel-Stadt beantragt ebenfalls die Abweisung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Die Beschwerdeführer rügen eine Verletzung des Rechtsgleichheitsgebotes von Art. 8 Abs. 1 BV, der verlangt, dass im öffentlichen Dienstrecht gleiche oder gleichwertige Arbeit gleich entlöhnt wird (<ref-ruling> E. 3.2). Dieser Anspruch ist - vorbehältlich anders lautender Regelungen, die hier nicht vorliegen - mit staatsrechtlicher Beschwerde durchzusetzen. Eine Diskriminierung im Sinne des Bundesgesetzes vom 24. März 1995 über die Gleichstellung von Frau und Mann (Gleichstellungsgesetz, GlG; SR 151.1), die mit Verwaltungsgerichtsbeschwerde zu rügen wäre, steht nicht in Frage und wird auch nicht geltend gemacht (vgl. angefochtenes Urteil E. 3a).
1.2 Die Beschwerdeführer sind durch die angefochtene Verweigerung der Rückwirkung ihrer höheren Einstufung in ihren rechtlich geschützten Interessen berührt und zur Beschwerde legitimiert (Art. 88 OG).
1.3 Auf die frist- und formgerecht eingereichte Beschwerde ist einzutreten.
2. Die Beschwerdeführer haben auf Grund der vom Appellationsgericht am 8. September 2000 festgestellten Ungleichbehandlung mit anderen im Erziehungsdepartement beschäftigten Lehrkräften mit gleichen Anforderungen und gleichem Pflichtenheft unbestrittenermassen Anspruch auf Einreihung in die Lohnklasse 17 (angefochtenes Urteil E. 4a). Streitig ist einzig, ob dieser Anspruch - wie das Appellationsgericht entschieden hat - erst für die Zeit seit dem 1. August 2001 besteht, oder aber - wie die Beschwerdeführer vorbringen - bereits seit dem 1. März 1996 bzw. dem späteren Datum ihres Stellenantrittes.
3. 3.1 Der Grundsatz der Rechtsgleichheit und damit Art. 8 Abs. 1 BV ist verletzt, wenn im öffentlichen Dienstverhältnis gleichwertige Arbeit ungleich entlöhnt wird. Innerhalb der Grenzen des Willkürverbots und des Rechtsgleichheitsgebots sind die Behörden befugt, aus der Vielzahl denkbarer Anknüpfungspunkte die Kriterien auszuwählen, die für die Besoldung von Beamten massgebend sein sollen. Verfassungsrechtlich ist nicht verlangt, dass die Besoldung allein nach der Qualität der geleisteten Arbeit bzw. den tatsächlich gestellten Anforderungen bestimmt wird. Ungleichbehandlungen müssen sich aber vernünftig begründen lassen bzw. sachlich haltbar sein. So hat das Bundesgericht erkannt, dass Art. 8 BV (bzw. Art. 4 Abs. 1 aBV) nicht verletzt ist, wenn Besoldungsunterschiede auf objektive Motive wie Alter, Dienstalter, Erfahrung, Familienlasten, Qualifikation, Art und Dauer der Ausbildung, Arbeitszeit, Leistung, Aufgabenbereich oder übernommene Verantwortlichkeiten zurückzuführen sind (<ref-ruling> E. 6a-c S. 7 f., mit Hinweisen; <ref-ruling> E. 7a). Dies gilt auch für den Bereich der Rechtsanwendung, in welchem die Behörden nach dem Grundsatz der Rechtsgleichheit verpflichtet sind, gleiche Sachverhalte mit gleichen relevanten Tatsachen gleich zu behandeln, es sei denn, ein sachlicher Grund rechtfertige eine unterschiedliche Behandlung (<ref-ruling> E. 3a).
Strengere Massstäbe gelten hingegen im Bereich der Lohngleichheit zwischen Mann und Frau (Art. 8 Abs. 3 Satz BV), wo der sonst grosse Ermessensspielraum der zuständigen Behörden erheblich eingeschränkt ist (vgl. Urteil 2P.369/1998 vom 21. März 2000 E. 3).
3.2 Das Appellationsgericht hat dazu festgehalten, die Wirkung der Einreihung in eine neue Lohnklasse beginne praxisgemäss auf den ersten Tag des auf den Antrag folgenden Monats. Zwar könnten besondere Gründe ausnahmsweise eine Rückwirkung rechtfertigen. Eine solche falle aber nicht in Betracht, wenn Mitarbeiter selber keinen Antrag auf Neueinreihung stellten oder ihren Vorgesetzten drängten, einen Antrag zu stellen. Der Mitarbeiter, der Risiko, Kosten und Umtriebe von Einsprache und Rekurs scheue, dürfe für eine beschränkte Übergangszeit schlechter gestellt werden als der Kollege, der die Einreihungsverfügung erfolgreich angefochten habe. Dem untätig gebliebenen Mitarbeiter komme deshalb der von einem Dritten erstrittene Prozesserfolg grundsätzlich erst ab dem Zeitpunkt des entsprechenden Rechtsmittelentscheides zugute.
3.3 Die Frage, wieweit der Anspruch auf (diskriminierungsfreien) Lohn auch für die Zeit vor Einreichung der Lohnklage geltend gemacht werden kann, wurde erstmals in BGE <ref-ruling> (E. 10 S. 449 ff.) näher erörtert. Das Bundesgericht stellte in jenem Entscheid fest, das Lohngleichheitsgebot sei ein unmittelbar anwendbares, justiziables subjektives Individualrecht, welches als solches - unter Vorbehalt der Verjährung - grundsätzlich auch nachträglich noch geltend gemacht werden könne. Dies müsse bei öffentlichrechtlichen Arbeitsverhältnissen gleichermassen möglich sein wie bei privatrechtlichen. Das Vorliegen einer Anstellungsverfügung stehe dem nicht entgegen, und ein gültiger Verzicht auf diskriminierungsfreien Lohn müsste in eindeutiger Form vorliegen; das blosse Zuwarten mit dem Geltendmachen der Forderung sei noch kein Rechtsmissbrauch. Da der Anspruch auf diskriminierungsfreien Lohn ein bundesrechtliches Individualrecht sei, gelte mangels einer Spezialregelung im Gleichstellungsgesetz die fünfjährige Verjährungsfrist gemäss Art. 128 Ziff. 3 OR.
In <ref-ruling> (E. 3 S. 16 ff.) bestätigte das Bundesgericht diese Rechtsauffassung und verwarf eine Reihe dagegen erhobener Argumente (Rechtssicherheit, Rechtsmissbrauchsverbot, Treu und Glauben).
3.4 Beide Entscheide - auf die sich auch die Beschwerdeführer stützen - heben hervor, dass ein Anspruch auf Nachzahlung des Lohnes schon unter der Herrschaft von Art. 4 Abs. 2 Satz 3 aBV anerkannt worden sei (vgl. insb. BGE <ref-ruling> E. 10c S. 450). Die herangezogenen Präjudizien betrafen - abgesehen vom nicht publizierten Urteil 2P.463/1996 vom 16. März 1998 - immer die Lohngleichheit zwischen Mann und Frau bzw. Ansprüche aus Art. 4 Abs. 2 Satz 3 aBV (so <ref-ruling>, 117 Ia 262, 118 Ia 35).
Das Bundesgericht fügte dem Hinweis auf diese Praxis in BGE <ref-ruling> (E. 10 S. 450) allerdings unter Berufung auf das unveröffentlichte Urteil 2P.463/1996 vom 16. März 1998 (E. 4 f.) bei, auch im Rahmen von Art. 4 Abs. 1 aBV sei das Bundesgericht stillschweigend davon ausgegangen, dass eine Verletzung dieser Bestimmung dem Betroffenen Anspruch auf Nachzahlung im Rahmen der Verjährungsfrist gebe.
Dieses Urteil betraf indessen einen wesentlich anders gelagerten Sachverhalt: Es ging um die Überführung von Wohnungszulagen in die ordentliche Besoldung der Angehörigen der St. Galler Kantonspolizei, wobei die bisherigen Bezüger dieser aufgehobenen Zulage während einer gewissen Übergangszeit gegenüber den bisherigen Nichtbezügern besser gestellt waren. Das Bundesgericht erblickte in dieser Besoldungsdifferenz mangels eines sachlichen Grundes eine Verletzung der Rechtsgleichheit. Es hob den betreffenden Entscheid auf und bemerkte in seinen Erwägungen (E. 5), es sei Sache der kantonalen Instanzen, zu prüfen, in welchem Umfang ein allfälliger Lohnnachzahlungsanspruch des Beschwerdeführers begründet sei.
3.5 Die Regel, wonach die Korrektur von diskriminierenden Löhnen von Bundesrechts wegen mit fünfjähriger Rückwirkung verlangt werden kann, wird denn auch in der Doktrin auf die spezielle Garantie der Lohngleichheit von Mann und Frau bzw. auf Ansprüche aus dem Gleichstellungsgesetz bezogen (Margrith Bigler-Eggenberger, St. Galler Kommentar, Rz. 97 zu Art. 8 BV; Hansjörg Seiler, Gleicher Lohn für gleichwertige Arbeit, in: ZBl 104/2003 S. 137 f.).
3.6 Dies zu Recht: Der Anspruch auf gleiche Entlöhnung von Mann und Frau ist nach dem Ausgeführten aufgrund von Spezialnormen in Art. 4 Abs. 2 Satz 3 aBV bzw. Art. 8 Abs. 3 BV sowie des Gleichstellungsgesetzes als subjektives Individualrecht ausgestaltet; bei Nachweis einer ungerechtfertigten Diskriminierung besteht damit ein direkter Anspruch auf einen diskriminierungsfreien Lohn, der im Rahmen der (bundesrechtlichen) Verjährungsregeln auch rückwirkend geltend gemacht werden kann. Bei ungleichen Besoldungen, die nicht geschlechtsspezifisch bedingt diskriminierend sind, liegen die Dinge anders: Hier gilt als Schranke lediglich das allgemeine Rechtsgleichheitsgebot von Art. 8 Abs. 1 BV, welches nicht unmittelbar ein subjektives Recht auf einen rechtsgleichen Lohn verschafft, sondern nur einen Anspruch auf Beseitigung der Ungleichheit und lediglich indirekt zur Folge haben kann, dass der öffentliche Arbeitgeber einem Betroffenen zur Beseitigung einer Rechtsungleichheit höhere Leistungen ausrichten muss.
3.7 Zwar wurde in der bundesgerichtlichen Rechtsprechung schon aus dem allgemeinen Rechtsgleichheitsgebot eine Verpflichtung des öffentlichen Arbeitgebers abgeleitet, gleichwertige Arbeit gleich zu entlöhnen; gleichzeitig wurde aber betont, dass den Behörden bei der Wahl der Anknüpfungspunkte für die Festsetzung der Besoldung innerhalb der Grenzen des Willkürverbotes ein weiter Gestaltungsspielraum zustehe (<ref-ruling> E. 6c S. 8, mit Hinweisen). Dieser Spielraum muss auch zuerkannt werden, wenn es - wie hier - darum geht, eine festgestellte (nicht geschlechtsspezifische) Rechtsungleichheit in der Besoldung zu beseitigen. Aus dem allgemeinen Rechtsgleichheitsgebot ergibt sich kein direkter bundesrechtlicher Anspruch auf rückwirkende Ausrichtung einer rechtsgleichen Besoldung, wie dies für den Bereich der Lohngleichheitsgarantie für Mann und Frau der Fall ist; von Verfassungs wegen kann lediglich verlangt werden, dass der rechtsungleiche Zustand auf geeignete Weise und in angemessener Frist behoben wird. Was die Angemessenheit der Frist anbelangt, so darf in vertretbarer Weise berücksichtigt werden, wann sich ein Betroffener erstmals gegen die beanstandete Rechtsungleichheit gewehrt hat. Es ist nicht unhaltbar, einen rechtsungleichen Zustand erst mit Wirkung ab jenem Zeitpunkt zu korrigieren, in dem durch den Betroffenen ein entsprechendes Begehren überhaupt gestellt worden ist. Für gewisse Bereiche, in denen eine rückwirkende Korrektur sachlich gar nicht stattfinden kann - z.B. bei bisher befolgten rechtsungleichen Verboten -, erscheint diese Konsequenz selbstverständlich. Aber auch bei Lohnforderungen, die an sich rückwirkend erfüllt werden können, erscheint es nicht stossend und willkürlich, die unter dem Titel der allgemeinen Rechtsgleichheit erforderliche Korrektur erst ab dem Zeitpunkt der Geltendmachung des entsprechenden Anspruches zu gewähren. Das lässt sich ohne weiteres begründen, wo der zu niedrige Lohn in Form einer anfechtbaren und in Rechtskraft erwachsenen Verfügung festgesetzt worden ist, doch kann die Beschränkung der Korrektur auf den künftigen Zeitraum auch dann eine verfassungsrechtlich ausreichende Massnahme darstellen, wenn der rechtsungleiche Lohn vom Betroffenen bis zur Geltendmachung des Anspruches widerspruchslos akzeptiert worden ist.
3.8 Mithin ergibt sich die Notwendigkeit einer rückwirkenden Lohnerhöhung im vorliegenden Fall, da keine geschlechtsspezifische Ungleichbehandlung in Frage steht, nicht aus der in der Beschwerdeschrift angerufenen Rechtsprechung in BGE <ref-ruling> und 125 I 14 zur Lohngleichheit für Mann und Frau bzw. aus der hierfür geltenden besonderen bundesrechtlichen Verjährungsregelung. Es kann sich nur darum handeln, ob die im angefochtenen Urteil angestellten Überlegungen zur Rechtfertigung der zeitlichen Differenzierungen für die Vornahme der Lohnkorrektur sachlich haltbar sind, d.h. insbesondere, ob es vertretbar ist, jene Lehrkräfte, welche das Risiko eines Prozesses auf sich genommen haben, früher in den Genuss des Lohnausgleiches kommen zu lassen als die übrigen, welche den Ausgang des Prozesses abwarten wollten bzw. ihre Ansprüche erst nach Kenntnis des betreffenden Rechtsmittelentscheides angemeldet haben. Eine solche Differenzierung erscheint nicht unvernünftig und ist auch mit dem Gerechtigkeitsgebot durchaus vereinbar.
3.9 Der weitere Einwand der Beschwerdeführer, sie hätten wegen der besonderen konkreten Umstände nach Treu und Glauben davon ausgehen dürfen, dass auch ihre Lohneinreihungen auf Grund des Ausganges des in Frage stehenden Verfahrens überprüft würden, ohne dass sie selber entsprechende Vorkehren zur Anfechtung ihrer Einreihungen hätten treffen müssen, geht fehl.
3.9.1 Die Beschwerdeführerinnen A._ und B._ wurden auf den 23. Juni 1997 bzw. 1. August 1998, d.h. nach dem Überführungsbeschluss vom 11. Juli 1995, definitiv als Lehrerinnen der Waldschule X._ gewählt und in die Lohnklasse 16 eingereiht. Nach den unbestrittenen Feststellungen des Appellationsgerichts haben beide im Zeitpunkt ihrer Wahl gewusst, dass andere Lehrerinnen und Lehrer gegen ihre Überführung in die Lohnklasse 16 gemeinsam ein Einsprache- und Rekursverfahren eingeleitet hatten und das Verfahren damals noch hängig war. Das Appellationsgericht durfte damit ohne Willkür davon ausgehen, dass den beiden Beschwerdeführerinnen - auch wenn ihre Anstellungsverfügungen allenfalls nicht mit Rechtsmittelbelehrungen versehen waren - hätte zugemutet werden können, bei der Wahl mindestens einen Vorbehalt in Bezug auf ihre Einreihung anzubringen. Dass sie davon durch konkrete Zusicherungen seitens der Behörden abgehalten worden wären, bringen sie nicht vor. Es kann im Übrigen auf die Ausführungen des Appellationsgerichts verwiesen werden (angefochtener Entscheid E. 4a und d).
3.9.2 Dem Beschwerdeführer C._ wurde die Überführung in die Lohnklasse 16 zunächst provisorisch eröffnet. In der Folge schrieb er dem Personalchef des Erziehungsdepartements, dass eigentlich Lohnklasse 17 zu erwarten wäre, worauf ihm dieser mitteilte, die Überführung sei richtig, die Einreihung aller Lehrkräfte mit Heilpädagogikdiplom werde aber überprüft. Am 27. Oktober 1995 erhielt der Beschwerdeführer dann die definitive Überführungsverfügung in Lohnklasse 16. Er hat diese indessen nicht angefochten. Bei dieser Sachlage durfte das Appellationsgericht ohne Willkür folgern, der Beschwerdeführer habe nun nicht mehr weiterhin darauf vertrauen dürfen, dass seine Einstufung noch überprüft werde. Der daraus gezogene Schluss, der Beschwerdeführer hätte nicht untätig bleiben dürfen, sondern Einsprache erheben müssen, wenn er seine Einstufung als unrichtig erachtete, ist nicht unhaltbar.
3.10 Das Appellationsgericht hat daher Art. 8 Abs. 1 BV nicht verletzt, wenn es den Anspruch der Beschwerdeführer auf Lohnnachzahlung erst seit dem 1. August 2001 anerkannt hat.
4. Die staatsrechtliche Beschwerde ist aus diesen Gründen abzuweisen. Bei diesem Ausgang haben die Beschwerdeführer die Kosten des Verfahrens vor Bundesgericht zu tragen (Art. 156 Abs. 1 und 7 OG).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 3'000.-- wird den Beschwerdeführern auferlegt, unter Solidarhaftung.
3. Dieses Urteil wird den Beschwerdeführern, dem Regierungsrat und dem Appellationsgericht, als Verwaltungsgericht, des Kantons Basel-Stadt schriftlich mitgeteilt.
Lausanne, 16. Februar 2005
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: