Sachverhalt:
A. A._ wurde am 3. August 2004 bedingt aus einer Freiheitsstrafe (5 Jahre wegen Drogendelikten) entlassen. Während der anschliessenden dreijährigen Probezeit für die Reststrafe von 637 Tagen beging er erneut Betäubungsmitteldelikte, weshalb ihn das Kriminalgericht des Kantons Luzern am 26. April 2007 unter anderem wegen mehrfacher qualifizierter Widerhandlung gegen das Betäubungsmittelgesetz zu 3 Jahren Freiheitsstrafe verurteilte. Dieses Urteil erwuchs in Rechtskraft, nachdem A._ seine dagegen eingereichte Appellation zurückgezogen hatte. Am 23. Januar 2008 entliess ihn das Justiz- und Sicherheitsdepartement des Kantons Luzern (Abteilung Vollzugs- und Bewährungsdienste) erneut bedingt aus dem Strafvollzug, worauf er am 26. Januar 2008 fremdenpolizeilich nach Albanien ausgeschafft wurde.
B. Aufgrund einer Meldung des Bundesamtes für Justiz (Schweizerisches Strafregister), in welcher auf die bedingte Entlassung vom 3. August 2004 hingewiesen wurde, widerrief das Kriminalgericht diese am 17. April 2008. Auf Rekurs von A._ hin hob das Obergericht des Kantons Luzern diesen Widerrufsentscheid am 26. August 2008 auf. Es entschied, dass die bedingte Entlassung gemäss Verfügung des Departements des Innern des Kantons Aargau vom 9. Juli 2004 nicht widerrufen werde.
C. Mit Beschwerde in Strafsachen beantragt die Staatsanwaltschaft des Kantons Luzern, der Entscheid des Obergerichtes sei aufzuheben und die Sache bezüglich der Widerrufsfrage zur erneuten Beurteilung an die Vorinstanz zurückzuweisen.
D. Während von Seiten des Beschwerdegegners keine Stellungnahme eingegangen ist, beantragt die Vorinstanz die Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Im Gegensatz zum Kriminalgericht ist die Vorinstanz der Auffassung, eine nachträgliche Anordnung der Rückversetzung in einem separaten Entscheid sei nicht möglich. Der Allgemeine Teil des Strafgesetzbuches sehe eine nachträgliche Abänderung des rechtskräftigen Sachurteils im Sanktionspunkt nicht vor. Vielmehr impliziere das Erfordernis, eine Gesamtstrafe bilden zu müssen, angesichts der Interdependenz von neuer Straftat und Reststrafe, dass diese auch unter dem Gesichtspunkt der Einheit der Materie im Strafurteil gebildet werden solle und müsse. Eine Zweiteilung des Verfahrens in Sachurteil und Entscheid über den Widerruf würde zu einem problematischen Eingriff in die Rechtskraft des Sachurteils führen. Rechtskraft bedeute die Verbindlichkeit eines Urteilsspruchs für spätere Prozesse, selbst wenn dieser unrichtig sei oder auf fehlerhaftem Verfahren beruhe. Nur so könnten Rechtsfrieden und Rechtssicherheit durchgesetzt werden. Der Betroffene müsse sich in der Regel auf den Bestand und damit die Unabänderlichkeit eines rechtskräftigen Urteils verlassen können. Dies müsse hier umso mehr zutreffen, als verschiedene rechtskräftige Sachurteile und Vollzugsentscheide, die vor dem Erlass des angefochtenen Entscheids ergingen, von diesem Entscheid direkt oder indirekt mehr oder weniger erheblich betroffen seien. Die erneute Sanktionierung von Straftaten, welche bereits in einem rechtskräftigen Urteil behandelt wurden, würde zudem das Prinzip "ne bis in idem" verletzen. Die Rechtslage sei angesichts des Eingriffs in die Rechtskraft des Sachurteils auch nicht mit der Möglichkeit vergleichbar, den bedingten Vollzug einer früheren Strafe nicht mit Sachurteil, sondern in einem separaten Entscheid des gleichen Gerichts zu prüfen. Nach altem Recht sei dies zugelassen gewesen, weil Art. 41 Abs. 3 (recte Ziff. 3) aStGB keine Gesamtstrafe verlangt habe und damit nicht in die Rechtskraft des Sachurteils eingegriffen worden sei.
1.2 Die Beschwerdeführerin macht demgegenüber im Wesentlichen geltend, dass bei einem irrtümlich unterbliebenen Rückversetzungsentscheid ein separater Entscheid vom Gesetz nicht ausgeschlossen sei. Der Sinn der Vorgehensregel in <ref-law> (Bildung einer Gesamtstrafe) müsse im Gesamtzusammenhang der Neuregelung des Strafzumessungs- und Vollzugswesens gesehen werden. Der bedingt Entlassene solle entsprechend <ref-law> beim Zusammentreffen der Rückfallstaten und dem Entscheid der Rückfallsanordnung nicht schlechter gestellt werden, als dies bei zwei separaten Entscheiden voraussichtlich der Fall wäre. Der Gesetzgeber habe eine Kumulation - wie unter dem alten Recht - verhindern wollen, indem die neue Strafe und der widerrufene Strafrest zusammengezählt würden. Er nehme mit der neuen Regelung darauf Bezug, dass es durchaus einen Unterschied machen könne, ob die neue, nicht besonders hohe Rückfallsstrafe mit einem langen Strafrest oder umgekehrt eine lange neue Strafe mit einem kurzen Strafrest zusammenfalle. Darum müsste bei einem separaten Rückfallsentscheid, wie ihn das Kriminalgericht wegen einer massiven einschlägigen Rückfälligkeit nachzuholen hatte, darauf Acht gegeben werden, dass ein hypothetisches Gesamturteil gefällt würde. Das Gericht müsste mithin sein rechtskräftiges Urteil als feststehende, unabänderliche Sanktion miteinbeziehen und diese dem noch zu fällenden "Vollzugsurteil" zugrunde legen. Auf diese Weise würde nicht in die Rechtskraft des bereits gefällten Sachurteils zu den Rückfallstaten eingegriffen.
2. Nach <ref-law> wird dem aus einer Freiheitsstrafe bedingt Entlassenen eine Probezeit auferlegt, deren Dauer dem Strafrest entspricht. 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. Es kann darauf verzichten, wenn nicht zu erwarten ist, dass der Verurteilte weitere Straftaten begehen wird. Dabei kann es den Verurteilten verwarnen und die Probezeit um höchstens die Hälfte verlängern (Art. 89 Abs. 1 und 2 StGB). Die Rückversetzung darf nicht mehr angeordnet werden, wenn seit dem Ablauf der Probezeit drei Jahre vergangen sind (<ref-law>). Sind auf Grund der neuen Straftat die Voraussetzungen für eine unbedingte Freiheitsstrafe erfüllt und trifft diese mit der durch den Widerruf vollziehbar gewordenen Reststrafe zusammen, so bildet das Gericht in Anwendung von Artikel 49 eine Gesamtstrafe (<ref-law>).
2.1 Wer bedingt aus dem Strafvollzug entlassen wird und während der Probezeit erneut ein Vergehen oder Verbrechen begeht, wird dafür entsprechend der üblichen strafrechtlichen und strafprozessualen Vorgaben vom zuständigen Gericht bestraft. Unter der Herrschaft des alten Rechts hatte unabhängig davon die Vollzugsbehörde darüber zu befinden, ob der bedingt Entlassene in den Strafvollzug zurückversetzt wurde (Art. 45 Ziff. 3 Abs. 1 aStGB). Nahm sie von einer Rückversetzung Umgang, konnte sie ihn verwarnen, ihm weitere Weisungen erteilen und die Probezeit verlängern (Art. 45 Ziff. 3 Abs. 4 aStGB). Nach neuem Recht hat nicht mehr die Vollzugsbehörde, sondern ein Gericht über die Rückversetzung zu entscheiden. Zuständig ist der Richter, der auch die neuen Straften zu beurteilen hat (<ref-law>), wie dies beim Widerruf des bedingten Strafvollzugs gilt (<ref-law>). In welcher prozessualen Form der Entscheid zu ergehen hat, ergibt sich aus dem Strafgesetzbuch nicht. Namentlich findet sich keine Regelung, ob die neue deliktische Tätigkeit und die Rückversetzung gleichzeitig zu beurteilen sind.
2.2 Während nach altem Recht mit dem Widerruf der bedingten Entlassung und der Ausfällung der neuen Strafe zwei grundsätzlich voneinander unabhängige Entscheide ergingen, hat der Gesetzgeber nunmehr vorgesehen, dass - im Falle einer unbedingten Freiheitsstrafe für das neue Delikt - eine Gesamtstrafe im Sinne von <ref-law> zu bilden ist (<ref-law>). Dies würde an sich bedeuten, dass entsprechend dem Asperationsprinzip von der schwersten Tat auszugehen und die entsprechende Strafe (Einsatzstrafe) für die anderen Taten angemessen zu erhöhen ist. Hat das Gericht eine Tat zu beurteilen, die der Täter begangen hat, bevor er wegen einer anderen Tat verurteilt worden ist, so bestimmt es die Zusatzstrafe in der Weise, dass der Täter nicht schwerer bestraft wird, als wenn die strafbaren Handlungen gleichzeitig beurteilt worden wären (<ref-law>). Damit soll das Asperationsprinzip auch bei retrospektiver Konkurrenz gewährleistet werden. Eine Zusatzstrafe kann sich etwa aufdrängen, wenn das erste Gericht die zusätzlichen Delikte nicht kannte, aber auch, wenn aus anderen Gründen nicht alle Straftaten beurteilt wurden. Immer geht es darum, dass der Täter, der mehrere Freiheitsstrafen verwirkt hat, nach einem einheitlichen, für ihn relativ günstigen Prinzip der Strafschärfung beurteilt werden soll, unabhängig davon, ob die Verfahren getrennt durchgeführt werden oder nicht. Der Täter soll durch die Aufteilung der Strafverfolgung in mehrere Verfahren weder benachteiligt noch besser gestellt werden (<ref-ruling> E. 8.2 S. 104 f. mit Hinweisen). Dieser Grundsatz kann dazu führen, dass nötigenfalls auf ein rechtskräftiges Urteil zurückgekommen wird: Ist jemand entgegen den Vorschriften über das Zusammentreffen mehrerer strafbarer Handlungen (<ref-law>) von mehreren Gerichten zu mehreren Freiheitsstrafen verurteilt worden, so setzt das Gericht, das die schwerste Strafe ausgesprochen hat, auf Gesuch des Verurteilten eine Gesamtstrafe fest (<ref-law>).
2.3 Es ist sachgerecht, diese Grundsätze auch anzuwenden, wenn entgegen der Regelung von <ref-law> keine Gesamtstrafe ausgesprochen worden ist. Hat das Gericht - aus welchen Gründen auch immer - die offene Reststrafe bei der Bemessung der neuen (unbedingten) Freiheitsstrafe nicht berücksichtigt, so muss dies ähnlich der Regelung von <ref-law> korrigiert werden können. Andernfalls würde die Rückversetzung in den Strafvollzug verunmöglicht, was der gesetzlichen Regelung von <ref-law> widerspräche, wonach diese Sanktion bei Nichtbewährung zwingend anzuordnen ist. Entgegen der Auffassung der Vorinstanz in ihrer Vernehmlassung kann es nicht darauf ankommen, ob der Verurteilte mit einem nachträglichen separaten Entscheid über die Rückversetzung zu rechnen hat oder nicht. Ein bedingt aus dem Strafvollzug Entlassener, der während der Probezeit rückfällig wird, muss davon ausgehen, dass über die Frage der Rückversetzung formell entschieden wird. Aus dem blossen Umstand, dass im neuen Strafurteil dazu nichts ausgeführt wird, lässt sich nicht herleiten, der Strafrest bleibe unangetastet. Selbst wenn der Betroffene sich darüber irren sollte, kann jedenfalls keine Rede davon sein, ein nachträglicher Widerruf sei nach Treu und Glauben ausgeschlossen. Weshalb im Übrigen das Prinzip "ne bis in idem" tangiert sein soll, ist nicht erkennbar. Bei der Bildung einer (nachträglichen) Gesamtstrafe werden die Straftaten, welche bereits in einem rechtskräftigen Urteil behandelt wurden, nicht erneut beurteilt, weshalb der Täter auch nicht zweimal verfolgt wird. Wie das Bundesgericht kürzlich entschieden hat (BGE 6B_765/2008 vom 7. April 2009 E. 2.4.1), ist bei der Bildung der Gesamtstrafe nach <ref-law> die neue Strafe als "Einsatzstrafe" durch einen zu widerrufenden Teil der noch offenen Reststrafe zu erhöhen. Die "Einsatzstrafe" bleibt damit unberührt und bei der "Erhöhungsstrafe" geht es um deren teilweisen nachträglichen Vollzug. Durch die sinngemässe Anwendung des Asperationsprinzips wird der rückfällige Täter im Vergleich zum Kumulationsprinzip sogar privilegiert (a.a.O.).
2.4 Indem die Vorinstanz materiell nicht über die Frage der Rückversetzung in den Strafvollzug entschieden hat, verletzt sie <ref-law>. Die Beschwerde ist deshalb gutzuheissen und die Sache zu neuer Entscheidung an die Vorinstanz zurückzuweisen. Diese wird im Sinne der erwähnten bundesgerichtlichen Rechtsprechung - auf die verwiesen werden kann - gegebenenfalls zu befinden haben, welchen Anteil der offenen Reststrafe des Urteils vom 3. August 2004 der Beschwerdegegner als "Zusatzstrafe" zum Urteil des Kriminalgerichtes des Kantons Luzern vom 26. April 2007 noch verbüssen muss.
3. Ausgangsgemäss sind keine Kosten zu erheben und ist keine Entschädigung zuzusprechen (Art. 66 und 68 Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, der Entscheid des Obergerichtes des Kantons Luzern (II. Kammer) vom 26. August 2008 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird der Beschwerdeführerin und dem Obergericht des Kantons Luzern, II. Kammer, schriftlich sowie dem Beschwerdegegner auf dem Ediktalweg mitgeteilt.
Lausanne, 22. April 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Binz