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.