Sachverhalt:
A. A._ und B._ (Beschwerdeführer) waren seit 1. April 2000 Mieter einer 4 1/2-Zimmerwohnung in Basel. Sie verlangen von der Vermieterin, der X._ (Beschwerdegegnerin), die Rückerstattung zu Unrecht bezahlter Nebenkosten in der Höhe von Fr. 14'117.60 nebst Zins zu 5 % seit 29. April 2005.
B. Nachdem vor der staatlichen Schlichtungsstelle für Mietstreitigkeiten keine Einigung erzielt werden konnte, gelangten die Mieter an das Zivilgericht Basel-Stadt, Dreiergericht. Sie beantragten, die Vermieterin zur Bezahlung von Fr. 14'117.60 nebst Zins zu 5 % seit 29. April 2005 zu verpflichten. Das Dreiergericht wies die Klage am 14. Februar 2006 ab. Eine gegen diesen Entscheid gerichtete Beschwerde der Mieter wies das Appellationsgericht des Kantons Basel-Stadt, Ausschuss, am 17. August 2006 ab.
Dagegen ergriffen die Beschwerdeführer sowohl Berufung als auch staatsrechtliche Beschwerde an das Bundesgericht. Mit Urteil vom 21. März 2007 hiess das Bundesgericht die staatsrechtliche Beschwerde gut und hob das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 17. August 2006 auf (Verfahren 4P.323/2006). Die Berufung schrieb es infolge Gegenstandslosigkeit ab (Verfahren 4C.427/2006).
Am 5. September 2007 entschied das Appellationsgericht erneut in dieser Sache: In Gutheissung der Beschwerde der Mieter hob es das Urteil des Dreiergerichts vom 14. Februar 2006 auf und wies die Sache zu neuem Entscheid im Sinne der Erwägungen an die Vorinstanz zurück.
C. Die Beschwerdeführer beantragen dem Bundesgericht mit subsidiärer Verfassungsbeschwerde, es sei das angefochtene Urteil aufzuheben.
Die Beschwerdegegnerin beantragt, auf die Beschwerde nicht einzutreten, eventualiter sei sie vollumfänglich abzuweisen. Die Vorinstanz beantragt, die Beschwerde abzuweisen, soweit überhaupt darauf eingetreten werden könne.

Erwägungen:
1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 2).
1.1 Nachdem vorliegend der für eine Beschwerde in Zivilsachen in mietrechtlichen Fällen erforderliche Streitwert von Fr. 15'000.-- (<ref-law>) nicht erreicht ist, fällt eine subsidiäre Verfassungsbeschwerde in Betracht (<ref-law>).
1.2 Die subsidiäre Verfassungsbeschwerde ist zulässig gegen Endentscheide, mithin solche, die das Verfahren abschliessen (Art. 90 i.V.m. <ref-law>). Der vorliegend angefochtene Rückweisungsentscheid schliesst das kantonale Verfahren nicht ab. Vielmehr weist er die Sache zu neuem Entscheid im Sinne der Erwägungen an die Erstinstanz zurück. Es handelt sich somit um einen selbständig eröffneten Zwischenentscheid (<ref-ruling> E. 1.3).
1.3 Gegen selbständig eröffnete Vor- und Zwischenentscheide, die weder die Zuständigkeit noch Ausstandsbegehren betreffen (<ref-law>), ist die Beschwerde zulässig, wenn sie einen nicht wieder gutzumachenden Nachteil bewirken können, oder wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (Art. 93 Abs. 1 i.V.m. <ref-law>). Die selbständige Anfechtbarkeit von Zwischenentscheiden bildet aus prozessökonomischen Gründen eine Ausnahme vom Grundsatz, dass sich das Bundesgericht mit jeder Angelegenheit nur einmal befassen soll (<ref-ruling> E. 2.1). Die Ausnahme ist restriktiv zu handhaben, zumal die Parteien keiner Rechte verlustig gehen, wenn sie einen Zwischenentscheid im Sinne von <ref-law> nicht selbständig anfechten, können sie ihn doch mit dem Endentscheid anfechten, soweit er sich auf dessen Inhalt auswirkt (<ref-law>; <ref-ruling> E. 3.2).
Es obliegt dem Beschwerdeführer darzutun, dass die Voraussetzungen von <ref-law> für eine selbständige Anfechtbarkeit eines Zwischenentscheids gegeben sind (<ref-ruling> E. 2.3.1 und 2.4.2; <ref-ruling> E. 3.2). Vorliegend äussern sich die Beschwerdeführer dazu mit keinem Wort und es ist auch nicht offensichtlich, dass die Voraussetzungen erfüllt wären. Auf die subsidiäre Verfassungsbeschwerde ist daher nicht einzutreten.
2. Bei diesem Verfahrensausgang werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2. Die Gerichtskosten von Fr. 500.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 7. April 2008
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Corboz Widmer