Sachverhalt:
A. X._ verbüsste in der Strafanstalt Lenzburg aufgrund verschiedener Verurteilungen aus den Jahren 1990, 1999 und 2002 eine mehrjährige Freiheitsstrafe. Mit Entscheid des Departements des Innern des Kantons Solothurn vom 24. August 2004 wurde er auf den 17. September 2004 bei einer Probezeit von 3 Jahren bedingt aus dem Strafvollzug entlassen.
Vor Ablauf der Probezeit delinquierte X._ erneut, indem er im Jahre 2006 in Mittäterschaft versuchte, Geldgeber dazu zu bringen, Vermögenswerte für in Wahrheit nicht vorhandene Anlagen zur Verfügung zu stellen.
B. Mit Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 29. Oktober 2008 wurde X._ zweitinstanzlich schuldig gesprochen des versuchten Betrugs. Das Appellationsgericht bestrafte ihn mit einer bedingten Freiheitsstrafe von 6 Monaten bei einer Probezeit von 3 Jahren sowie mit einer unbedingten Geldstrafe von 180 Tagessätzen à Fr. 30.--, ohne über einen Widerruf der bedingten Entlassung aus dem Strafvollzug zu entscheiden. Mit Urteil vom 23. Dezember 2009 ordnete das Appellationsgericht die Rückversetzung in den Strafvollzug an (Reststrafe ohne Berücksichtigung allfälliger Vollzugsverjährungen 678 Tage).
C. X._ gelangt mit Beschwerde in Strafsachen ans Bundesgericht. Er beantragt, das Urteil des Appellationsgerichts des Kantons Basel-Stadt sei aufzuheben, und es sei auf die Rückversetzung in den Strafvollzug zu verzichten.
D. Vernehmlassungen wurden keine eingeholt.

Erwägungen:
1. Die Vorinstanz beurteilt die Frage der Nichtbewährung bzw. Rückversetzung nach neuem Recht. In Anwendung der übergangsrechtlichen Regelung von <ref-law>, ergänzt durch Ziff. 1 Abs. 3 der Schlussbestimmungen der Änderung des Strafgesetzbuches vom 13. Dezember 2002 sowie entsprechend der bundesgerichtlichen Rechtsprechung (Urteil des Bundesgerichts 6B_303/2007 vom 6. Dezember 2007 E. 4.3, mit Hinweis auf <ref-ruling>) ist dies nicht zu beanstanden.
2. 2.1 Der Beschwerdeführer bringt vor, er habe im vorinstanzlichen Verfahren dargetan und mit den entsprechenden Urkunden belegt, dass er seit 2006/2007 als Student mit Fernstudium an der rechtswissenschaftlichen Fakultät der Universität AAB in Pristina, Kosovo, immatrikuliert sei und ordentlich das Studium besuche. Zudem sei er mit Arbeitsvertrag vom 22. Juli 2009 als Administrator einer Handelsgesellschaft in Pristina angestellt. Auch habe das Gemeindegericht in Dekan, Kosovo, schriftlich bestätigt, dass er in seinem Heimatstaat in kein Strafverfahren verwickelt sei. Indem die Vorinstanz auf ihr Urteil vom 29. Oktober 2008 verweise, wonach bei der Verübung des versuchten Betrugs gefälschte Urkunden eingesetzt worden seien, unterstelle sie ihm, er habe die nun eingereichten Dokumente gefälscht. Dies sei unzulässig. Dass er nicht persönlich an der Verhandlung erschienen sei, dürfe ihm nicht zum Nachteil gereichen. Das persönliche Erscheinen sei fakultativ gewesen. Auch bestehe nach wie vor ein Landesverweis, weshalb das Erscheinen zur vorinstanzlichen Verhandlung mit grossem administrativen Aufwand verbunden gewesen wäre. Er sei in seiner Heimat vollständig integriert. Die Vorinstanz habe einzig seine kriminelle Vergangenheit sowie die Tatsache berücksichtigt, dass er die Delikte in der Schweiz auch vom Ausland aus begangen habe. Sie habe auf eine Gesamtwürdigung aller für die Prognose relevanten Umstände verzichtet und deshalb ihr Ermessen überschritten (Beschwerde S. 3 ff.).
2.2 Hat sich der bedingt Entlassene bis zum Ablauf der Probezeit bewährt, so ist er endgültig zu entlassen (<ref-law>). Begeht er während der Probezeit ein Verbrechen oder Vergehen, so ordnet das für die Beurteilung der neuen Tat zuständige Gericht die Rückversetzung an (<ref-law>). Ist trotz des während der Probezeit begangenen Verbrechens oder Vergehens nicht zu erwarten, dass der Verurteilte weitere Straftaten begehen wird, so verzichtet das Gericht auf eine Rückversetzung (<ref-law>).
Nach dieser Regelung ist die Rückversetzung grundsätzlich anzuordnen, wenn der bedingt Entlassene während der Probezeit ein Verbrechen oder Vergehen begangen hat, es sei denn, es handle sich um eine blosse "Zufallstat", die nicht unbesehen darauf schliessen lässt, er werde weiter delinquieren. Die Anforderungen an eine günstige Prognose sind zwar strenger als bei der Gewährung des bedingten Strafvollzuges eines Ersttäters nach <ref-law>, dagegen grosszügiger als beim Wiederholungstäter nach <ref-law>. Angesichts der bloss relativen Sicherheit von Legalprognosen dürfen an die Erwartung, dass keine weiteren Straftaten begangen werden, keine übermässig hohen Anforderungen gestellt werden. Wie beim Entscheid über die bedingte Entlassung muss genügen, wenn dies vernünftigerweise erwartet werden darf. Für die prognostische Bewertung der neuen Straftat (<ref-law>) können die vom Bundesgericht entwickelten Prognosekriterien für die Gewährung des bedingten Strafvollzuges (<ref-law>) beigezogen werden. So ist bei der Prüfung, ob der Verurteilte für ein dauerndes Wohlverhalten Gewähr bietet, eine Gesamtwürdigung aller wesentlichen Umstände vorzunehmen. In die Beurteilung mit einzubeziehen sind neben den Tatumständen auch das Vorleben und der Leumund sowie alle weiteren Tatsachen, die gültige Schlüsse auf den Charakter des Täters und die Aussichten seiner Bewährung zulassen. Für die Einschätzung des Rückfallrisikos ist ein Gesamtbild der Täterpersönlichkeit unerlässlich.
Relevante Faktoren sind etwa strafrechtliche Vorbelastung, Sozialisationsbiographie und Arbeitsverhalten, das Bestehen sozialer Bindungen, Hinweise auf Suchtgefährdungen usw. Dabei sind die persönlichen Verhältnisse bis zum Zeitpunkt des Entscheides mit einzubeziehen. Es ist unzulässig, einzelnen Umständen eine vorrangige Bedeutung beizumessen und andere zu vernachlässigen oder überhaupt ausser Acht zu lassen. Wie bei der Strafzumessung (<ref-law>) müssen die Gründe im Entscheid so wiedergegeben werden, dass sich die richtige Anwendung des Bundesrechts überprüfen lässt (<ref-ruling> E. 4.2.1 S. 5). Bei der Beurteilung der Bewährungsaussicht steht dem zuständigen Gericht ein Ermessensspielraum zu. Das Bundesgericht greift nur ein, wenn das Gericht sein Ermessen über- oder unterschritten oder missbraucht und damit Bundesrecht verletzt hat. Eine Ermessensüberschreitung kann etwa darin liegen, auf eine Gesamtwürdigung aller für die Prognose relevanten Umstände zu verzichten und auf die Vorstrafen allein abzustellen (<ref-ruling> E. 2.3 S. 204; zum Ganzen und mit weiteren Hinweisen: Urteil 6B_303/2007 vom 6. Dezember 2007 E. 6).
2.3 Der am 17. September 2004 bedingt entlassene Beschwerdeführer hat unbestrittenermassen während der Probezeit delinquiert. Die Vorinstanz geht von einer ungünstigen Prognose aus. Ins Zentrum ihrer Erwägungen stellt sie die zahlreichen Vorstrafen. Sie erwägt, dass die Angaben des Beschwerdeführers über die Aufnahme eines Studiums sowie die Arbeitstätigkeit nicht überprüfbar seien (angefochtenes Urteil S. 3). Im Schreiben der Universität AAB in Pristina wird dem Beschwerdeführer die Teilnahme am ordentlichen (Fern-) Studium attestiert. Gemäss Arbeitsvertrag vom 22. Juli 2009 nahm der Beschwerdeführer gleichentags seine Tätigkeit bei einer Handelsgesellschaft in Pristina auf. Diese Urkunden unterliegen der freien Beweiswürdigung durch die Vorinstanz. Soweit der Beschwerdeführer vorbringt, er habe durch diese Unterlagen aufgezeigt, dass er das Studium der Rechtswissenschaft ordentlich besuche und bei einer Handelsgesellschaft tätig sei, legt er einzig dar, wie diese Beweismittel seiner Auffassung nach richtigerweise zu würdigen gewesen wären. Eine willkürliche Beweiswürdigung macht er nicht geltend (vgl. dazu <ref-ruling> E. 1.3 S. 4 f.) und wäre im Übrigen durch das appellatorische Vorbringen des Beschwerdeführers nicht dargetan. Selbst wenn der Beschwerdeführer das Studium der Rechtswissenschaft, das er im Jahre 1984 nach einem Semester abgebrochen hatte (Urteil des Obergerichts des Kantons Zürich vom 1. Oktober 2009 S. 62), wieder aufgenommen hätte, böte dies für ein dauerndes Wohlverhalten keine Gewähr. Im Übrigen ist die vorinstanzliche Beweiswürdigung im Ergebnis nicht verfassungswidrig. Die Arbeitstätigkeit, welche der Beschwerdeführer gemäss seiner Darstellung seit dem 22. Juli 2009 ausübt, wurde im vorinstanzlichen Verfahren nicht näher umschrieben, und weitere Ausführungen zum Arbeitgeber, Arbeitsort, Umfeld etc. fehlen. Der behauptete Einstieg ins Berufsleben bleibt mithin wenig substanziiert, was die Vorinstanz willkürfrei als nicht glaubhaft beurteilen darf.
Der Beschwerdeführer weist gemäss Auszug aus dem Strafregister vom 31. August 2009 sechs, teilweise mehrjährige Vorstrafen auf, welche die Vorinstanz berücksichtigen darf (Art. 369 Abs. 1 und 2 StGB). Zusätzlich wurde er mit Entscheid des Obergerichts des Kantons Zürich vom 1. Oktober 2009 zweitinstanzlich schuldig gesprochen des gewerbsmässigen Betrugs sowie der mehrfachen Urkundenfälschung und mit einer unbedingten Freiheitsstrafe von zwei Jahren bestraft. Eine dagegen erhobene Beschwerde ans Bundesgericht wurde mit Urteil vom 29. April 2010 (6B_23/2010) abgewiesen. Auch diese Verurteilung ist zu berücksichtigen. Bereits am 17. Dezember 1991 wurde der Beschwerdeführer von der Regierung des Kantons Graubünden per 17. Juli 1992 bedingt aus dem Strafvollzug entlassen. Am 21. April 1999 wurde die Rückversetzung verfügt. Die mit Entscheid des Obergerichts des Kantons Zürich vom 1. Oktober 2009 beurteilten Delikte beging der Beschwerdeführer ab April bis Mai 2002. Damals musste er, nebst einer zehnjährigen Landesverweisung, mit dem Vollzug einer mehrjährigen Freiheitsstrafe (drei Verurteilungen sowie eine Rückversetzung in den Strafvollzug, alle aus dem Jahre 1999) rechnen, was ihn nicht von weiteren Straftaten abhielt.
Ebenso wenig zeigte sich der Beschwerdeführer im Jahre 2004 beeindruckt, als er zum zweiten Mal aus dem Strafvollzug vorzeitig entlassen und aus der Schweiz ausgewiesen wurde. Es wurde ihm eine dreijährige Probezeit angesetzt, wobei ihm für den Fall der Nichtbewährung ein verbleibender Strafrest von 678 Tagen drohte. Die mit Entscheid des Appellationsgerichts des Kantons Basel-Stadt vom 29. Oktober 2008 zweitinstanzlich beurteilten Delikte nahmen bereits im Jahre 2005 ihre Anfänge. Damals kam der Beschwerdeführer mit mehreren Personen zusammen, die er teilweise während des Strafvollzugs in der Strafanstalt Lenzburg kennengelernt hatte. Die Gruppierung beabsichtigte, längerfristig Geldgeber dazu zu bringen, in Anlagen zu investieren, die in Wahrheit nicht existierten. Ihren Plan setzte sie Ende April / Anfang Mai 2006 (ohne Erfolg) um. Bereits im April und Mai 2002 war der Beschwerdeführer an einem Betrugskonzept (Wechselfinanzierung) zum Nachteil von zahlreichen Kreditsuchenden beteiligt. Der Beschwerdeführer knüpfte somit nach seiner bedingten Entlassung relativ nahtlos an frühere Taten an, dies sowohl in zeitlicher Hinsicht als auch in Bezug auf die Art der verübten respektiv versuchten Delikte. Eine "Zufallstat" (E. 2.2 hievor) liegt nicht vor.
Die vorinstanzliche Würdigung lässt sich nicht beanstanden, zumal die dargestellten Umstände in ihrer Gesamtheit eine ungünstige Prognose nahelegen. Endlich ist auch nicht zu rügen, dass die Vorinstanz schwergewichtig auf die strafrechtliche Vorbelastung des Beschwerdeführers abstellt. Unbestritten ist einerseits, dass der Beschwerdeführer an der vorinstanzlichen Hauptverhandlung nicht teilnahm und deshalb nicht ergänzend befragt werden konnte. Sein Vorbringen, wonach die Einreise in die Schweiz mit einem grossen administrativen Aufwand verbunden gewesen wäre (Beschwerde S. 4), ist unbehelflich. Er macht zu Recht nicht geltend, dass es ihm nicht möglich gewesen wäre, persönlich zur vorinstanzlichen Verhandlung zu erscheinen. Vielmehr ist anzunehmen und Gegenteiliges ist nicht dargetan, dass das Eidgenössische Justiz- und Polizeidepartement die über ihn verhängte Einreisesperre, wie in der Vergangenheit wiederholt geschehen, suspendiert hätte. Andererseits zeigt der Beschwerdeführer weder im vorinstanzlichen noch im bundesgerichtlichen Verfahren in seinen Eingaben auf, inwiefern sich seine aktuelle Situation (nebst dem vorgebrachten Studium und der Anstellung) verfestigt haben sollte respektive eine nachhaltige positive Veränderung seiner Lebensumstände eingetreten wäre (vgl. vorinstanzliche Akten, Eingabe vom 26. Oktober 2009). Substanziierte Ausführungen zu allfälligen sozialen Bindungen in seinem Heimatland, seiner behaupteten Arbeitstätigkeit von 40 Stunden pro Woche und seinem gleichzeitigen Studium an der rechtswissenschaftlichen Fakultät in Pristina fehlen.
3. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang sind die bundesgerichtlichen Kosten dem Beschwerdeführer aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 17. Mai 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Faga