Sachverhalt:
A. Das Bundesstrafgericht verurteilte X._ am 19. September 2007 wegen versuchten Einführens falschen Geldes zu einer Freiheitsstrafe von 16 1/2 Monaten, wovon es 6 Monate unbedingt und 10 1/2 Monate bedingt aussprach.
B. Mit Beschwerde in Strafsachen beantragt X._, Ziffer 2 des vorinstanzlichen Urteils sei aufzuheben und ihm sei - bei einer Probezeit von 3 Jahren - der bedingte Strafvollzug zu gewähren. Zudem stellt er den Antrag auf unentgeltliche Rechtspflege.
C. Die Vorinstanz hat auf eine Vernehmlassung verzichtet, während die Bundesanwaltschaft in ihrer Stellungnahme beantragt, die Beschwerde sei gutzuheissen.

Erwägungen:
1. Der Beschwerdeführer macht geltend, die Vorinstanz gehe zu Recht davon aus, dass ihm keine ungünstige Prognose ausgestellt werden könne. Er habe sich seit dem Vorfall vom 16. Mai 2004 wohlverhalten. Der Strafaufschub nach <ref-law> sei die Regel. Die Vorinstanz halte in ihrer Begründung lapidar fest, ihn würde ein grosses Verschulden treffen. Diesem Verschulden sei jedoch bereits bei der Höhe der Strafe Rechnung getragen worden. Es könne nicht angehen, dass ihm deswegen auch noch der bedingte Strafvollzug teilweise verwehrt werde. Ein teilbedingter Vollzug sei nur zu bejahen, wenn der Aufschub wenigstens eines Teils der Strafe aus spezialpräventiver Sicht verlange, dass der andere Teil vollzogen werde. Diese Frage habe die Vorinstanz nicht geprüft und damit auch die Begründungspflicht verletzt.
1.1 Bei Freiheitsstrafen im überschneidenden Anwendungsbereich von Art. 42/43 StGB (zwischen einem und zwei Jahren) ist der Strafaufschub nach <ref-law> die Regel, die grundsätzlich vorgeht. Der teilbedingte Vollzug bildet dazu die Ausnahme. Sie ist nur zu bejahen, wenn der Aufschub wenigstens eines Teils der Strafe aus spezialpräventiver Sicht erfordert, dass der andere Strafteil unbedingt ausgesprochen wird. Damit verhält es sich ähnlich wie bei der Beurteilung der Bewährungsaussichten im Fall eines Widerrufs einer bedingt ausgesprochenen Freiheitsstrafe. Ergeben sich - inbesondere aufgrund früherer Verurteilungen - ganz erhebliche Bedenken an der Legalbewährung des Täters, die bei einer Gesamtwürdigung aller Umstände eine eigentliche Schlechtprognose noch nicht zu begründen vermögen, so kann das Gericht an Stelle des Strafaufschubs den teilbedingten Vollzug gewähren. Auf diesem Wege kann es im Bereich höchst ungewisser Prognosen dem Dilemma "Alles oder Nichts" entgehen. <ref-law> hat die Bedeutung, dass die Warnwirkung des Teilaufschubes angesichts des gleichzeitig angeordneten Teilvollzuges für die Zukunft eine weitaus bessere Prognose erlaubt. Erforderlich ist aber stets, dass der teilweise Vollzug der Freiheitsstrafe für die Erhöhung der Bewährungsaussichten unumgänglich erscheint. Das trifft nicht zu, solange die Gewährung des bedingten Strafvollzugs, kombiniert mit einer Verbindungsgeldstrafe bzw. Busse (<ref-law>), spezialpräventiv ausreichend ist. Diese Möglichkeit hat das Gericht vorgängig zu prüfen (<ref-ruling> E. 5.5.2 S. 14 f., mit Hinweisen).
1.2 Die Vorinstanz hält in ihrem Entscheid fest, nach heutiger Sicht sei beim Beschwerdeführer von einer nicht ungünstigen Prognose auszugehen. Ein unbedingter Vollzug sei nicht notwendig, um ihn von weiteren Verbrechen und Vergehen abzuhalten. Der Beschwerdeführer sei innerhalb der letzten fünf Jahre vor der Tat zu keiner Strafe gemäss Abs. 2 des <ref-law> verurteilt worden. Das Kriterium der Schadenbehebung sei vorliegend nicht von Belang. Die Voraussetzungen einer bedingten Strafe würden somit vorliegen. Den Beschwerdeführer treffe jedoch ein grosses Verschulden, welches eine vollständig bedingte Strafe nicht mehr rechtfertigen könne, weshalb die Strafe teilbedingt auszusprechen sei.
1.3 Mit dieser Begründung steht die Vorinstanz nicht im Einklang mit der neuen bundesgerichtlichen Rechtsprechung. Sie geht selbst davon aus, dem Beschwerdeführer könne keine ungünstige Prognose gestellt werden. Aufgrund ihrer Erwägungen bestehen keine Bedenken an seiner Legalbewährung. Somit ist ein teilweiser Vollzug der Strafe nicht notwendig, um ihn von der Begehung weiterer Delikte abzuhalten. Weil es nach der erwähnten Rechtsprechung auf das Verschulden nicht ankommen kann, sind die Voraussetzungen für den bedingten Strafvollzug nach <ref-law> erfüllt. Indem die Vorinstanz den Vollzug der Freiheitsstrafe von 16 1/2 Monaten nur teilweise aufschob, verletzte sie Bundesrecht.
2. Die Beschwerde ist deshalb gutzuheissen. Da dem obsiegenden Beschwerdeführer bei diesem Ausgang keine Kosten aufzuerlegen sind (<ref-law>), wird sein Gesuch um unentgeltliche Rechtspflege gegenstandslos. Nachdem die Bundesanwaltschaft wegen ihres Antrages auf Gutheissung der Beschwerde nicht unterliegt, rechtfertigt es sich, den Rechtsvertreter des Beschwerdeführers aus der Bundesgerichtskasse zu entschädigen (vgl. Art. 68 Abs. 1 und 2 sowie <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, der Entscheid des Bundesstrafgerichtes vom 19. September 2007 aufgehoben und die Sache zur Neubeurteilung an die Vorinstanz zurückgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird als gegenstandslos abgeschrieben.
3. Es werden keine Kosten erhoben.
4. Der Rechtsvertreter des Beschwerdeführers wird für das bundesgerichtliche Verfahren mit Fr. 3'000.-- aus der Bundesgerichtskasse entschädigt.
5. Dieses Urteil wird den Parteien und dem Bundesstrafgericht, Strafkammer, schriftlich mitgeteilt.
Lausanne, 15. April 2008
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Schneider Binz