Sachverhalt:
A. Der mazedonische Staatsangehörige X._ (geb. ***1968) war von September 1991 bis September 1992 in Mazedonien mit seiner Landsfrau A._ verheiratet. Nach der Scheidung hielt sich X._ bis zu seiner Ausschaffung am 17. Februar 1995 illegal in der Schweiz auf. Im August 1995 heiratete er in Mazedonien eine 23 Jahre ältere Schweizer Bürgerin und reiste am 25. Mai 1997 zum Verbleib bei der Ehefrau in die Schweiz ein. Am 22. Mai 2002 wurde ihm die Niederlassungsbewilligung erteilt. Ein Gesuch um erleichterte Einbürgerung schrieb das Bundesamt für Migration am 6. Juni 2006 ab, nachdem es X._ mit dem Vorwurf, es könnte eine Scheinehe vorliegen, konfrontiert hatte und dieser sich nicht mehr vernehmen liess. Am 13. Dezember 2006 wurde die Ehe von X._ mit seiner schweizerischen Ehefrau geschieden.
Mit der ersten Ehefrau A._ hat X._ zwei erst nach der Scheidung von der Kindsmutter geborene Kinder B._ (geb. ***1992) und C._ (geb. ***1996). Die Kinder leben bei ihrer Mutter und den Grosseltern in Mazedonien. Mit Urteil des Kreisgerichts Tetowo vom 20. Juni 2005 wurden sie unter das Sorgerecht des Vaters gestellt.
B. Am 22. April 2005 stellte X._ ein erstes Gesuch um Nachzug der Kinder, das vom Migrationsamt des Kantons Basel-Stadt am 3. März 2006 abgewiesen wurde. Das Sicherheitsdepartement (heute Justiz- und Sicherheitsdepartement) sowie das Appellationsgericht des Kantons Basel-Stadt (Urteil vom 20. April 2007) haben diesen Entscheid bestätigt.
Am 22. Oktober 2008 stellte X._ erneut ein Gesuch um Nachzug seiner beiden Kinder. Zur Begründung führte er im Wesentlichen aus, nach dem am 1. Januar 2008 in Kraft getretenen Ausländergesetz dürfe beim Familiennachzug nicht mehr zwischen gemeinsam und getrennt lebenden Eltern unterschieden werden. Das Migrationsamt trat mit Verfügung vom 4. Dezember 2008 mangels neuer Tatsachen auf das Gesuch nicht ein. Das Justiz- und Sicherheitsdepartement wies den Rekurs gegen den Nichteintretensentscheid mit Entscheid vom 30. Juni 2008 (recte 30. Juni 2009) ab. Die dagegen erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht mit Urteil vom 23. November 2009 (zugestellt am 18. Januar 2010) ebenfalls ab. Die kantonalen Rechtsmittelinstanzen gingen davon aus, dass die Anwendung des neuen Rechts zu keinem andern Ergebnis geführt hätte.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 16. Februar 2010 beantragt X._, die Verfügung des Migrationsamts des Kantons Basel-Stadt vom 4. Dezember 2008 aufzuheben und den Kindern B._ und C._ die Einreise und den Aufenthalt in der Schweiz zu bewilligen, eventualiter das Sicherheitsdepartement (Migrationsamt) anzuweisen, das Familiennachzugsgesuch materiell zu entscheiden. Mit Eingabe vom 17. Februar 2010 änderte der Beschwerdeführer das Rechtsbegehren insofern, als mit der eingereichten Beschwerde einzig die Aufhebung des Urteils des Appellationsgerichts des Kantons Basel-Stadt vom 23. November 2009 beantragt wird.
Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt schliesst auf Abweisung der Beschwerde. Das Appellationsgericht des Kantons Basel-Stadt hat auf Vernehmlassung verzichtet. Das Migrationsamt des Kantons Basel-Stadt liess sich nicht vernehmen. Das Bundesamt für Migration hat unter Verweis auf die neueste Rechtsprechung des Bundesgerichts auf einen Antrag verzichtet.

Erwägungen:
1. 1.1 Gemäss Art. 83 lit. c Ziff. 2 BGG ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt. Der in der Schweiz niedergelassene Beschwerdeführer hat am 22. Oktober 2008, somit nach dem Inkrafttreten des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG: SR 142.20) darum ersucht, seine zu diesem Zeitpunkt 15 Jahre und 10 Monate bzw. 12 Jahre und 6 Monate alten Kinder in die Schweiz nachziehen zu können. Hierauf bestand grundsätzlich ein Anspruch (Art. 43 in Verbindung mit Art. 126 Abs. 3 AuG). Auf die Beschwerde ist somit einzutreten. Ob die (einzelnen) Bewilligungsvoraussetzungen gegeben sind, ist eine Frage der materiellen Beurteilung; für das Eintreten genügt, dass ein potentieller Anspruch auf den Nachzug besteht (vgl. BGE 2C_606/2009 vom 17. März 2010 E. 1 mit Hinweis).
1.2 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist nur gegen kantonal letztinstanzliche richterliche Entscheide zulässig (Art. 86 BGG). Soweit der Beschwerdeführer vorerst die Aufhebung der Verfügung des Migrationsamts vom 4. Dezember 2008 und die Bewilligung des Familiennachzugs verlangte, hätte auf sein Begehren nicht eingetreten werden können; der entsprechende Entscheid gilt jedoch inhaltlich als mitangefochten (<ref-ruling> E. 1 S. 441; <ref-ruling> E. 1c S. 33). Nachdem der Beschwerdeführer ausschliesslich das Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht anficht, bildet einzig die Frage Verfahrensgegenstand, ob sich das Migrationsamt wegen der neuen Rechtslage mit dem Gesuch vom 22. Oktober 2008 hätte materiell befassen müssen.
1.3 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Neue Tatsachen und Beweise dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Der Lohnausweis vom 24. Januar 2010, die Bestätigung des Arbeitgebers vom 9. Februar 2010 und das Schreiben der Kinder mit Übersetzung vom 3. Februar 2010 sind neu und können nicht berücksichtigt werden; sie wären ohnehin nicht geeignet, am Ausgang des vorliegenden Verfahrens etwas zu ändern.
2. 2.1 Nach der bundesgerichtlichen Praxis zu Art. 29 BV ist eine Verwaltungsbehörde von Verfassungs wegen verpflichtet, auf ein neues Gesuch einzutreten, wenn die Umstände sich seit dem ersten Entscheid wesentlich geändert haben oder wenn der Gesuchsteller erhebliche Tatsachen und Beweismittel namhaft macht, die ihm im früheren Verfahren nicht bekannt waren oder die schon damals geltend zu machen für ihn rechtlich oder tatsächlich unmöglich war oder keine Veranlassung bestand (<ref-ruling> E. 2.1 S. 181 mit Hinweis).
2.2 Ob ein neues Gesuch in Fällen wie dem vorliegenden materiell zu behandeln ist, hängt davon ab, ob sich der Sachverhalt oder bei Dauersachverhalten die Rechtslage in einer Art geändert hat, dass ein anderes Ergebnis ernstlich in Betracht fällt (vgl. die Urteile 2C_274/2009 vom 28. Oktober 2009 E. 2.2 und 2A.476/2005 vom 9. Mai 2006 E. 2, je mit Hinweisen). Wird im Zusammenhang mit einem Sachverhalt, der nach rechtskräftigem Abschluss des ursprünglichen ausländerrechtlichen Verfahrens anhält, ein neuer Antrag gestellt, wobei sich der Gesuchsteller auf eine geänderte Rechtslage beruft, besteht ein Anspruch auf einen neuen Sachentscheid nur, wenn er darlegt, dass und inwiefern sich die massgebende Rechtslage nachträglich wesentlich verändert hat; dabei genügt es nicht, dass er lediglich darauf hinweist, dass neues Recht in Kraft getreten ist, um kurz nach Abschluss eines Verfahrens einen Anspruch auf Neubefassung mit dem gleichen Lebenssachverhalt zu begründen; es ist vielmehr im Einzelnen darzulegen, inwiefern das neue Recht zu einer anderen Beurteilung führen muss (BGE 136 ll 177 E.2.2.1 S. 182 f. mit Hinweis).
2.3 In Anwendung des früheren Rechts (Art. 17 Abs. 2 ANAG) und der entsprechenden Rechtsprechung, die zwischen Zusammenführung der Gesamtfamilie und der Teilfamilie unterschied, wurde der Nachzug der Kinder des Beschwerdeführers mit Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 20. April 2007 rechtskräftig abgewiesen. Anders als bei zusammenlebenden Eltern, bei denen es für den nachträglichen Familiennachzug lediglich das Verbot des Rechtsmissbrauchs vorbehielt (vgl. <ref-ruling> E. 3.1.2 S. 14 mit Hinweis), verneinte das Bundesgericht in seiner Rechtsprechung zu Art. 17 Abs. 2 ANAG beim Nachzug zu einem Elternteil das Bestehen eines bedingungslosen Anspruchs. Es verlangte hierfür besondere familiäre Gründe bzw. eine zwingend notwendig gewordenen Änderung in den Betreuungsverhältnissen (<ref-ruling> E. 3.1 S. 9 f.; <ref-ruling> E. 2.2 S. 4; <ref-ruling> E. 3.1.2 und 3.1.3 S. 14 f.; <ref-ruling> E. 3a S. 366).
2.4 Der Gesetzgeber hat im Ausländergesetz den Familiennachzug grundlegend neugestaltet (vgl. <ref-ruling> E. 4 S. 80 ff.) und in den Übergangsbestimmungen (Art. 126 AuG) geregelt, wie der Systemwechsel vollzogen werden soll: Ausländische Ehegatten und ledige Kinder unter 18 Jahren von Personen mit Niederlassungsbewilligung haben Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie (1) mit diesen zusammenwohnen (Art. 43 Abs. 1 AuG), (2) der Nachzug innerhalb von fünf Jahren und bei Kindern über zwölf Jahren innerhalb von zwölf Monaten erfolgt (Art. 47 Abs. 1 AuG), (3) der Anspruch nicht rechtsmissbräuchlich geltend gemacht wird und zudem (4) kein Widerrufsgrund nach Art. 63 AuG vorliegt (vgl. Art. 51 Abs. 1 AuG). Die Fristen beginnen bei Familienangehörigen von Ausländerinnen und Ausländer mit der Erteilung der Aufenthalts- und Niederlassungsbewilligung oder der Entstehung des Familienverhältnisses (Art. 47 Abs. 3 lit. b AuG). Ist die Einreise vor dem Zeitpunkt des Inkrafttretens des Ausländergesetzes erfolgt oder das Familienverhältnis vor diesem entstanden, läuft die Nachzugsfrist ab dem 1. Januar 2008 (Act. 126 Abs. 3 AuG).
2.5 Der Beschwerdeführer hat während der Übergangsfrist von Art. 126 Abs. 3 AuG ein Gesuch um Nachzug seiner beiden Kinder, die damals 15 Jahre und zehn Monate bzw. 12 Jahre und 6 Monate alt und damit noch nicht 18-jährig waren, gestellt.
Die gesetzliche Übergangsregelung sieht vor, dass bei Kindern über 12 Jahren in Fällen wie dem vorliegenden die Nachzugsfrist (Art. 47 Abs. 1 AuG) mit dem Inkrafttreten des Ausländergesetzes zu laufen beginnt. Mit der Regelung von Art. 126 Abs. 3 AuG sollte gerade bereits anwesenden, niedergelassenen Ausländern bzw. Schweizer Staatsangehörigen ermöglichen, von der neuen Nachzugsregelung allenfalls noch profitieren zu können, ansonsten ihr Anspruch unter Umständen bereits erloschen wäre, bevor er überhaupt entstehen konnte. Auch wenn sich den Materialien nicht entnehmen lässt, dass vorübergehend eine materielle Rechtslage gewollt gewesen wäre, wonach Kinder im Nachzug zugelassen würden, für die ein solcher weder nach der bisherigen Praxis zum ANAG noch nach der neuen gesetzlichen Ordnung möglich erschiene, ist der Wortlaut von Art. 126 Abs. 3 AuG doch unzweideutig und klar. Entsprechende Nachzüge waren zeitlich beschränkt nur während eines Jahres möglich; diese Frist ist seit dem 1. Januar 2009 abgelaufen, sodass die übergangsrechtliche Besserstellung bereits anwesender Ausländer oder Schweizer, die von der altrechtlichen Nachzugsmöglichkeiten keinen oder erfolglos Gebrauch gemacht haben, vor dem verfassungsrechtlichen Gleichbehandlungsgebot und dem Verhältnismässigkeitsgebot standhält (vgl. Urteil 2C_606/2009 vom 17. März 2010 E. 2.3).
Beim Kindesverhältnis handelt es sich grundsätzlich um einen Dauersachverhalt. Der Beschwerdeführer hat in seinem Gesuch vom 22. Oktober 2008 dargelegt, dass das neue Recht für ihn günstiger sei, da in der Doktrin davon ausgegangen werde, dass die gestützt auf den Wortlaut von Art. 17 ANAG gemachte Unterscheidung zwischen dem Nachzug von Kindern bis zu 18 Jahren zu den gemeinsamen Eltern bzw. demjenigen zu nur einem Elternteil unter dem neuen Recht (Art. 43 Abs. 1 AuG) nicht mehr gelten könne. Da das Bundesgericht sich seinerzeit zu dieser Frage noch nicht geäussert hatte, wäre das Migrationsamt gehalten gewesen, das neue Gesuch an die Hand zu nehmen; es hätte dieses nicht durch einen Nichteintretensentscheid erledigen dürfen, und das Justiz- und Sicherheitsdepartement sowie das Appellationsgericht hätten die gegen diesen Nichteintretensentscheid gerichteten Beschwerden gutheissen müssen, zumal das Bundesgericht inzwischen mit Urteil vom 15. Januar 2010 die Auffassung verworfen hat, dass die bisherige Rechtsprechung, die zwischen nachträglichem Gesamt- und nachträglichem Teilfamiliennachzug unterschied, auch für die neue Regelung von Art. 43 in Verbindung mit Art. 47 und Art. 126 Abs. 3 AuG gilt (vgl. <ref-ruling>).
2.6 Das angefochtene Urteil ist somit aufzuheben und die Sache zur materiellen Prüfung des Nachzugsgesuchs an das Migrationsamt des Kantons Basel-Stadt zurückzuweisen.
3. Dem Verfahrensausgang entsprechend sind keine Kosten geschuldet (Art. 66 Abs. 4 BGG). Der unterliegende Kanton Basel-Stadt hat den obsiegenden Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 BGG). Das Appellationsgericht des Kantons Basel-Stadt wird über die kantonale Kosten- und Entschädigungsregelung neu zu befinden haben (vgl. Art. 67 BGG e contrario).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und das Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 23. November 2009 wird aufgehoben. Die Sache wird zu materiellem Entscheid an das Migrationsamt des Kantons Basel-Stadt zurückgewiesen.
2. 2.1 Es werden keine Kosten erhoben.
2.2 Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000 zu entschädigen.
2.3 Zur Regelung der kantonalen Kosten-und Entschädigungsfrage wird die Sache an das Appellationsgericht des Kantons Basel-Stadt zurückgewiesen.
3. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt des Kantons Basel-Stadt, dem Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 8. November 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Zünd Dubs