Sachverhalt:
A. X._ wurde mit Verfügung der zuständigen Behörde des Kantons St. Gallen der Führerausweis für die Zeit vom 24. Juni bis 23. September 2006 entzogen. Trotzdem fuhr er am 4. September 2006, um 15.25 Uhr, mit einem Personenwagen von Italien kommend bis zum Schweizer Zoll in Castasegna, wo ihn die Grenzbeamten anhielten und kontrollierten. Das Zollgebäude bzw. die Kontrollstelle befindet sich rund 35 Meter hinter der italienisch-schweizerischen Grenze und somit auf Schweizer Territorium.
B. Der Kreispräsident Bergell verurteilte X._ mit Strafmandat vom 14. November 2006 wegen Führens eines Motorfahrzeugs trotz Führerausweisentzugs zu 20 Tagen Haft und Fr. 5'000.-- Busse. Nach Einsprache von X._ bestätigte der Bezirksgerichtsausschuss Maloja mit Urteil vom 1. April 2008 den Schuldspruch und verurteilte ihn zu einer Geldstrafe von 10 Tagessätzen zu je Fr. 870.-- sowie zu einer Busse von Fr. 5'000.--. Das Kantonsgericht von Graubünden, Kantonsgerichtsausschuss, hiess mit Urteil vom 22. Oktober 2008 die von X._ dagegen erhobene Berufung teilweise gut und verurteilte ihn zu einer Busse von Fr. 2'000.--. Es verzichtete auf den Widerruf der mit Strafmandat des Untersuchungsamtes St. Gallen vom 28. August 2006 angeordneten bedingten Gefängnisstrafe von 8 Wochen, verlängerte jedoch die festgesetzte Probezeit um ein Jahr.
C. Mit Beschwerde in Strafsachen beantragt X._, das Urteil des Kantonsgerichts sei aufzuheben, und er sei von Schuld und Strafe freizusprechen. Eventualiter sei er der fahrlässigen Widerhandlung gegen <ref-law> schuldig zu sprechen, wobei von einer Bestrafung wegen Vorliegens eines besonders leichten Falls abzusehen sei. Subeventualiter sei von einer Bestrafung wegen geringfügiger Schuld und Tatfolgen abzusehen. Subeventualiter sei er mit einer Busse von höchstens Fr. 2'000.-- zu bestrafen, wobei auf eine Verlängerung der Probezeit für die bedingte Gefängnisstrafe des Untersuchungsamtes St. Gallen zu verzichten sei.
D. Die Vorinstanz beantragt die Abweisung der Beschwerde, soweit auf sie einzutreten ist. Demgegenüber verzichtet die Staatsanwaltschaft auf Vernehmlassung.

Erwägungen:
1. Am 1. Januar 2007 ist der revidierte Allgemeine Teil des Strafgesetzbuches in Kraft getreten. Dieses neue Recht gelangt jedoch auf Taten, welche noch in Geltung des alten Rechts begangen wurden, nur zur Anwendung, wenn es für den Täter das mildere ist (<ref-law> i.V.m. <ref-law>). Die Vorinstanz beurteilt das alte Recht als milder, weil im konkreten Fall eine Busse und nicht - wie nach neuem Recht - eine bedingte Geldstrafe und zusätzlich eine Busse auszufällen sei (vgl. angefochtenes Urteil E. 6d S. 15). Dem ist nicht beizustimmen. Die Vorinstanz hält eine unbedingte Strafe nicht für notwendig, um den Beschwerdeführer von der Begehung weiterer Verbrechen oder Vergehen abzuhalten (<ref-law>). Ist die Geldstrafe bedingt auszusprechen, ist sie gegenüber der Busse die mildere, weil weniger eingriffsintensive Sanktion (<ref-ruling> E. 7.2.4 S. 91). Im Rahmen der Strafenkombination von <ref-law> soll die Busse nicht zu einer Straferhöhung führen oder eine zusätzliche Strafe ermöglichen (<ref-ruling> E. 5.2 S. 55). Die Vorinstanz hat in Anwendung des alten Rechts eine Busse von Fr. 2'000.-- ausgesprochen. Da die Verbindungsbusse nach neuem Recht (<ref-law>) tiefer auszufallen hat, erweist sich dieses als das mildere.
2. Die Beschwerde richtet sich gegen die Verurteilung wegen Führens eines Motorfahrzeugs trotz Führerausweisentzugs. Der Beschwerdeführer rügt zunächst eine offensichtlich unrichtige Feststellung des Sachverhalts (<ref-law>).
2.1 Der Sachverhalt ist in objektiver Hinsicht unbestritten. In subjektiver Hinsicht führt die Vorinstanz aus, der Beschwerdeführer habe keine Anstalten gemacht, direkt am Kontrollposten einen Fahrerwechsel mit seiner Frau vorzunehmen, sondern habe dies gemäss eigenen Aussagen erst am nächstmöglichen Abstellplatz vornehmen wollen. Zwar sei beim Passieren der Grenze nicht auf Anhieb ersichtlich, wo genau diese verlaufe. Hätte der Beschwerdeführer aber mit Sicherheit vermeiden wollen, einige Meter auf Schweizer Territorium zu fahren, hätte er vor dem italienischen Grenzposten den Fahrerwechsel vornehmen können. Da es ihm unklar gewesen sei, wo die Grenze verlief, habe er in Kauf genommen, den Fahrerwechsel unter Umständen erst nach der Grenze vorzunehmen. Somit müsse sich der Beschwerdeführer den Vorwurf eventualvorsätzlichen Handelns gefallen lassen (angefochtenes Urteil E. 5c.dd S. 9 f.).
2.2 Der Beschwerdeführer bringt vor, die Vorinstanz habe fälschlicherweise festgestellt, dass er von sich aus keine Anstalten gemacht habe, direkt am Kontrollposten den Fahrerwechsel vorzunehmen. Er sei gleich nach dem Anhalten des Fahrzeugs zum Zwecke des Fahrerwechsels ausgestiegen. Beim Aushändigen der ID-Karte habe er von sich aus erklärt, er und seine Frau hätten ab der Grenze einen Fahrerwechsel beabsichtigt. Die Verhältnisse vor Ort seien nicht eindeutig gewesen, so dass es ihm nicht bewusst gewesen sei, einige Meter auf schweizerischem Staatsgebiet zu fahren. Entgegen der vorinstanzlichen Ausführung seien die Grenzmarken vom Auto aus nicht nur kaum, sondern gar nicht zu sehen gewesen. Er habe den Fahrerwechsel vor, und nicht kurz nach der Schweizer Grenze vollziehen wollen.
2.3 Vorsätzlich begeht ein Verbrechen oder Vergehen, wer die Tat mit Wissen und Willen ausführt. Vorsätzlich handelt bereits, wer die Verwirklichung der Tat für möglich hält und in Kauf nimmt (<ref-law>).
Was der Täter wusste, wollte und in Kauf nahm, betrifft sogenannte innere Tatsachen, ist damit Tatfrage. Rechtsfrage ist hingegen, ob im Lichte der festgestellten Tatsachen der Schluss auf Eventualvorsatz begründet ist (<ref-ruling> E. 4.1 S. 17 mit Hinweisen).
2.4 Die Vorinstanz hält selber fest, dass der genaue Grenzverlauf unklar sei. Die Ausführungen des Beschwerdeführers zu den unübersichtlichen Verhältnissen sind deshalb unbehelflich. Weiter legt der Beschwerdeführer nicht substantiiert dar, inwiefern der Schluss der Vorinstanz, er habe in Kauf genommen, den Fahrerwechsel erst kurz nach der Grenze vorzunehmen, schlechterdings unhaltbar ist (vgl. <ref-ruling> E. 3.1 S. 178 mit Hinweisen). Seine Vorbringen erschöpfen sich in einer unzulässigen appellatorischen Kritik am angefochtenen Urteil und genügen folglich den Begründungsanforderungen gemäss <ref-law> nicht (<ref-ruling> E. 1.4.3 S. 254 f. mit Hinweis). Auf seine Rüge ist nicht einzutreten, weshalb der (subjektive) Sachverhalt als erstellt gilt.
3. Weiter rügt der Beschwerdeführer die Verletzung der Bestimmung über den Eventualvorsatz.
3.1 Der Beschwerdeführer macht geltend, er habe die falsche Rechtsauskunft erhalten, trotz Fahrausweisentzugs in der Schweiz im Ausland fahren zu dürfen, weshalb er den Wagen bis an die Schweizergrenze gelenkt habe. Da er der Auffassung gewesen sei, das Territorium der Schweiz beginne beim Zollgebäude, sei er einem Sachverhaltsirrtum unterlegen. Die Vorinstanz habe den Sachverhalt nicht so beurteilt, wie er ihn sich vorgestellt habe. Er hätte den Irrtum auch bei pflichtgemässer Vorsicht nicht vermeiden können und sei deshalb von Schuld und Strafe frei zu sprechen. Falls die Vorinstanz davon ausgehe, dass er den Irrtum bei pflichtgemässer Vorsicht hätte vermeiden können, so komme lediglich eine Bestrafung wegen fahrlässiger Begehung in Frage. Weil er den eingetretenen Erfolg nicht als möglich habe voraussehen können, habe er auch nicht darauf vertrauen können, dass dieser Erfolg nicht eintrete. Damit wären auch die Voraussetzungen einer grobfahrlässigen Begehung nicht gegeben. Wegen der unübersichtlichen Verhältnisse vor Ort und der kurzen Fahrstrecke von 35 Metern wäre bei Annahme der fahrlässigen Widerhandlung gegen <ref-law> von der Bestrafung wegen Vorliegens eines besonders leichten Falls (<ref-law>) abzusehen. Die Vorinstanz habe zu Unrecht ein mittelschweres Verschulden angenommen. Da die Schuld gering sei und keine Tatfolgen gegeben seien, sei auch ein Verzicht auf die Bestrafung nach <ref-law> möglich.
3.2 Wie die Vorinstanz verbindlich festgestellt hat, wusste der Beschwerdeführer, dass ihm der Grenzverlauf unklar war. Diese Unklarheit ist auf seine eigene Gleichgültigkeit zurückzuführen. Ohne sich näher zu informieren, hat er sich bewusst fürs Nichtwissen entschieden. Dieses Nichtwissen wird nicht als Irrtum behandelt, so dass kein Sachverhaltsirrtum (<ref-law>) vorliegt (vgl. <ref-ruling> E. 2.3.1 S. 17).
Aufgrund seines fehlenden Wissens um den Grenzverlauf hat der Beschwerdeführer in Kauf genommen, einige Meter auf Schweizer Territorium zu fahren (S. E. 2.1 hiervor). Die Vorinstanz hat von diesem Wissen und Willen auf Eventualvorsatz geschlossen (s. <ref-ruling> E. 3.2.2 S. 28 f. mit Hinweisen und angefochtenes Urteil E. 5f S. 11). Inwiefern die Verurteilung wegen eventualvorsätzlichen Führens eines Motorfahrzeugs trotz Führerausweisentzugs (<ref-law>) Bundesrecht verletzt, ist nicht ersichtlich. Im Übrigen wird dies vom Beschwerdeführer auch nicht näher dargelegt.
Angesichts der Tatsache, dass der Beschwerdeführer eventualvorsätzlich handelte, ist es vertretbar, dass die Vorinstanz das Vorliegen eines besonders leichten Falls nach <ref-law> verneint. Weiter begründet der Beschwerdeführer nicht rechtsgenügend, inwiefern von einer Strafe gemäss <ref-law> abzusehen ist. Auch auf seinen Eventualantrag, von einer Verlängerung der Probezeit für die bedingte Freiheitsstrafe sei abzusehen, ist mangels Begründung nicht einzutreten.
3.3 Hingegen ist dem Beschwerdeführer beizustimmen, dass angesichts der kurzen Fahrstrecke von 35 Metern nicht von einem mittelschweren Verschulden gesprochen werden kann. Die Vorinstanz wird dies bei der Strafzumessung, welche sie nach neuem Recht vorzunehmen haben wird (vgl. E. 1 hiervor), zu berücksichtigen haben.
4. Demgemäss ist die Beschwerde teilweise gutzuheissen. Im Übrigen ist sie abzuweisen, soweit darauf einzutreten ist. Der Beschwerdeführer wird im Umfang seines Unterliegens kostenpflichtig (<ref-law>). Der Kanton Graubünden hat ihn für das bundesgerichtliche Verfahren zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen, der Entscheid des Kantonsgerichts von Graubünden vom 22. Oktober 2008 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Kanton Graubünden hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Kantonsgericht von Graubünden, Kantonsgerichtsausschuss, schriftlich mitgeteilt.
Lausanne, 20. Mai 2009
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Binz