Sachverhalt:
A. Die Bundesanwaltschaft erhob am 31. März 2008 Anklage gegen X._. In der Folge sprach ihn das Bundesstrafgericht mit Entscheid vom 8. Januar 2009 der mehrfachen qualifizierten Widerhandlung gegen das Betäubungsmittelgesetz schuldig und verurteilte ihn zu einer teilbedingten Freiheitsstrafe von 18 Monaten. Zudem verfügte es die Einziehung von drei sichergestellten Mobiltelefonen und setzte eine Ersatzforderung von Fr. 1'150.-- für den Erlös aus dem Drogenhandel fest.
B. Mit Beschwerde in Strafsachen beantragt X._, das Urteil des Bundesstrafgerichts sei aufzuheben, und die Sache im Sinne der Erwägungen zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem ersucht X._ um unentgeltliche Rechtspflege und Verbeiständung.
C. Das Bundesstrafgericht und die Bundesanwaltschaft beantragen, die Beschwerde sei abzuweisen, bzw. sei abzuweisen, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Die Anklageschrift vom 31. März 2008 wirft dem Beschwerdeführer vor, er habe in der Periode von 1996 bis 23. Januar 1999 hauptsächlich im Kanton Zürich und anderswo 680 g bis höchstens 8 kg Kokaingemisch an Zwischenhändler bzw. Endabnehmer verkauft und eventuell abgegeben, indem er:
a. von 1996 bis 23. Januar 1999 A._ mindestens 440 g bis höchstens 3,3 kg Kokaingemisch (Reinheitsgrad 41 % bzw. 75 %) zu einem Preis von Fr. 55.-- bis Fr. 60.-- pro Gramm verkauft habe;
b. von 1998 bis 1999 B._ mindestens 100 g bis höchstens 450 g Kokaingemisch (Reinheitsgrad durchschnittlich 42,7 %) zu einem Preis von Fr. 50.-- bis Fr. 65.-- pro Gramm verkauft habe;
c. von 1998 bis 1999 C._ mindestens 100 g bis höchstens 3,9 kg Kokaingemisch (Reinheitsgrad 41 %) verkauft habe (Anklageziffern A. 1. lit. a-c, kantonale Akten cl. 72 pag. 72.100.001 ff.; s. angefochtenes Urteil E. 1.1.1. S. 15).
1.2 Die Vorinstanz hält als erstellt, dass der Beschwerdeführer je mindestens 400 g Kokain an A._ sowie C._ und B._ (direkt oder via A._) und daher insgesamt mindestens 1'200 g Kokain verkauft hat, indem er die Drogen diesen Personen entgeltlich überliess (angefochtenes Urteil E. 1.1.5 S. 20).
2. 2.1 Der Beschwerdeführer rügt eine Verletzung des Anklageprinzips im Zusammenhang mit dem Anspruch auf ein faires Verfahren. Die drei Anklagepunkte würden die Voraussetzungen des Anklagegrundsatzes nicht erfüllen. Eine Anklageschrift, welche das deliktische Verhalten in einer Periode von über drei Jahren festlege, erschwere die Verteidigung in einem nicht mehr akzeptablem Ausmass und verletze dadurch gleichermassen das Anklageprinzip wie den Grundsatz des fair trial nach Art. 6 EMRK. Die Anklage setze ihn nicht in allen Einzelheiten über die Art und Weise seiner angeblichen Kokainlieferung an A._ in Kenntnis. Dieser habe zu seinen Drogenübernahmen verschiedene zeitliche Angaben gemacht. Die Anklageschrift erwähne nicht, ob er auf einmal oder in mehreren bzw. in wie vielen Malen er an A._ geliefert haben soll. Es genüge nicht, wenn die Anklage auf diverse Aktenstellen verweise, wo sich divergierende Aussagen über das Tatgeschehen fänden. Die Anklageschrift sei in zeitlicher und örtlicher Hinsicht sowie in Bezug auf die Tatausführung nicht hinreichend konkretisiert.
2.2 Die vorliegend zu beurteilende Anklageschrift wirft dem Beschwerdeführer den Verkauf von Kokaingemisch an mehrere Drogenabnehmer vor. Sie führt die drei Käufer, den Reinheitsgehalt des Kokains, den Deliktszeitraum von 1996 bis 23. Januar 1999 bzw. von 1998 bis 1999, sowie die Deliktsorte Zürich und "anderswo" auf. Die Vorinstanz hält fest, die in der Anklageschrift vermerkten Zeit-, Mengen- und Ortsangaben würden eine sehr weite Bandbreite umfassen. Dennoch führt sie aus, dem Beschwerdeführer sei es möglich gewesen, die gegen ihn erhobenen Vorwürfe zu verstehen (angefochtenes Urteil E. 2 S. 13).
2.3 Der Anklagegrundsatz wird abgeleitet aus Art. 29 Abs. 2 und Art. 32 Abs. 2 BV sowie Art. 6 Ziff. 1 und Ziff. 3 lit. a und b EMRK. Nach diesem Grundsatz bestimmt die Anklage das Prozessthema. Gegenstand des gerichtlichen Verfahrens können danach nur Sachverhalte sein, die dem Angeklagten in der Anklageschrift vorgeworfen werden (Umgrenzungsfunktion; Immutabilitätsprinzip). Die Anklageschrift muss die Person des Angeklagten sowie die ihm zur Last gelegten Delikte in ihrem Sachverhalt so präzise umschreiben, dass die Vorwürfe im objektiven und subjektiven Bereich genügend konkretisiert sind. Das Anklageprinzip bezweckt damit zugleich den Schutz der Verteidigungsrechte des Angeklagten und dient dem Anspruch auf rechtliches Gehör (Informationsfunktion; <ref-ruling> E. 6.3 S. 245; <ref-ruling> E. 2a S. 21 je mit Hinweisen).
Gemäss Art. 169 Abs. 1 des Bundesgesetzes vom 15. Juni 1934 über die Bundesstrafrechtspflege (BStP; SR 312.0) hat das Gericht nur die Taten zu beurteilen, auf die sich die Anklage bezieht. Es berücksichtigt die während des Vorverfahrens und in der Hauptverhandlung gemachten Feststellungen (Art. 169 Abs. 2 BStP). Die Anklageschrift bezeichnet u.a. den Angeklagten, das strafbare Verhalten, dessen er beschuldigt wird, nach seinen tatsächlichen und gesetzlichen Merkmalen und die Bestimmungen des Strafgesetzes, die anzuwenden sind (Art. 126 Abs. 1 BStP). Überzeugt sich der Bundesanwalt im Laufe der Hauptverhandlung, dass die Tat ein anderes Vergehen darstellt oder schwerer strafbar ist, als er angenommen hatte, so kann er die Anklage berichtigen (Art. 166 Satz 1 BStP).
Gemäss Art. 169 Abs. 1 des Bundesgesetzes vom 15. Juni 1934 über die Bundesstrafrechtspflege (BStP; SR 312.0) hat das Gericht nur die Taten zu beurteilen, auf die sich die Anklage bezieht. Es berücksichtigt die während des Vorverfahrens und in der Hauptverhandlung gemachten Feststellungen (Art. 169 Abs. 2 BStP). Die Anklageschrift bezeichnet u.a. den Angeklagten, das strafbare Verhalten, dessen er beschuldigt wird, nach seinen tatsächlichen und gesetzlichen Merkmalen und die Bestimmungen des Strafgesetzes, die anzuwenden sind (Art. 126 Abs. 1 BStP). Überzeugt sich der Bundesanwalt im Laufe der Hauptverhandlung, dass die Tat ein anderes Vergehen darstellt oder schwerer strafbar ist, als er angenommen hatte, so kann er die Anklage berichtigen (Art. 166 Satz 1 BStP).
2.4 2.4.1 Unter dem Gesichtspunkt der Informationsfunktion des Anklageprinzips ist massgebend, dass die angeklagte Person genau weiss, was ihr angelastet wird, damit sie ihre Verteidigungsrechte angemessen ausüben kann. Insbesondere soll es ihr möglich sein, die Tatvorwürfe, z.B. durch entsprechende Gegenfragen an Belastungszeugen oder ein Alibi, zu entkräften. Der vorinstanzlichen, knapp begründeten Auffassung, die Anklageschrift genüge den bundes- und verfassungsrechtlichen Anforderungen, ist nicht beizustimmen. Die Anklage umschreibt weder in zeitlicher, örtlicher noch sachlicher Hinsicht die dem Beschwerdeführer zur Last gelegten Drogengeschäfte in hinreichend konkreter Weise. So nennt sie die lange Zeitspanne von rund drei Jahren (1996 bis 23. Januar 1999) für die Drogenverkäufe an A._ sowie von 2 Jahren (1998 und 1999) für die entsprechenden Geschäfte mit B._ und C._. Sie bezeichnet den Deliktsort mit "Kanton Zürich und anderswo". Im Weiteren ist der Anklageschrift weder zu entnehmen, in wievielen Malen die Kokainverkäufe stattgefunden haben sollen, noch welche Mengen jeweils verkauft wurden. Die Gesamtmenge des Kokaingemisches von insgesamt "680 g bis höchstens 8 kg" variiert innerhalb einer weiten Bandbreite. Mit solch pauschalen Angaben kann sich der Beschwerdeführer nicht mehr sachgerecht und wirksam verteidigen. So ist es ihm beispielsweise unmöglich, lückenlos nachzuweisen, wann er sich wo im Zeitraum von 2 bzw. 3 Jahren befunden hat und was er dort getan hat. Ebenso ist das Deliktsgebiet mit dem gesamten Kanton Zürich und überall sonst ("anderswo") zu unbestimmt. Der Anspruch auf ein faires Verfahren nach Art. 6 EMRK und das daraus abgeleitete Anklageprinzip verbieten derartige, nicht näher konkretisierten Vorwürfe.
2.4.2 Aus den in der Anklageschrift enthaltenen Verweisen auf diverse Aktenstellen ergeben sich keine präziseren Erkenntnisse über die Tatorte, die Zeitpunkte und Anzahl der Drogenverkäufe sowie die gehandelten Mengen. Die genannten Dokumente enthalten hinsichtlich der dem Beschwerdeführer zur Last gelegten Taten unterschiedliche, widersprüchliche oder ungenaue Angaben, weshalb sich die angeklagten Taten nicht näher eingrenzen lassen. So geht etwa das Urteil des Tribunal pénal de l'arrondissement de la Broye vom 16. November 2001 von zwei Drogenverkäufen des Beschwerdeführers an A._ im Februar 1998 und von drei Fällen anfangs 1998 aus, in welchen dieser Drittpersonen zum Drogenkauf beim Beschwerdeführer begleitete. Demgegenüber berichtete A._ in der Einvernahme vom 31. Mai 2006 (act. 12-09-155 ff.) von zahlreichen, regelmässigen Kokaingeschäften mit dem Beschwerdeführer in den Jahren 1996 bis 1999. Auch die Aussagen von C._ (act. 12-07-0110: er habe 1998 total 110 Gramm Kokain beim Beschwerdeführer gekauft; act. 13-02-0262: er könne keine genauen Quantitätsangaben machen, er habe vor 10 Jahren, d.h. im Jahr 1997, von Zeit zu Zeit 20 Gramm Kokain beim Beschwerdeführer besorgt) und B._ (act. 13-02-0237: er habe 1998 vom Beschwerdeführer 100 Gramm Kokain gekauft) enthalten ungenaue zeitliche bzw. mengenmässige Angaben. Insgesamt konkretisiert die Anklageschrift die zu beurteilenden Taten nicht hinreichend. Der blosse Umstand, dass die Anklage die am Kokainhandel beteiligten Personen aufführt, vermag die anderen Unklarheiten, d.h. was der Beschwerdeführer wann, wo und wie getan hat, nicht aufzuwiegen. Die Verurteilung des Beschwerdeführers verletzt den Anklagegrundsatz. Die Beschwerde ist gutzuheissen und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen.
2.5 Fehl geht der Einwand des Beschwerdeführers, die Anklage sei von der Beschwerdegegnerin im Laufe der Hauptverhandlung unzulässigerweise abgewandelt worden, indem ihm zur Last gelegt werde, er habe C._ 3.9 kg Kokain verkauft. Denn der entsprechende Vorwurf ergibt sich bereits aus der Anklageschrift selbst (S. 4 lit. A.1.c).
3. Der Beschwerdeführer wendet sich weiter gegen die Einziehung der Mobiltelefone. Es sei ihm nie vorgeworfen oder nachgewiesen worden, dass er Mobiltelefone zur Begehung einer Straftat benutzt habe oder habe benutzen wollen.
3.1 Gemäss <ref-law> verfügt das Gericht die Einziehung von Gegenständen, die zur Begehung einer Straftat gedient haben oder bestimmt waren oder die durch eine Straftat hervorgebracht worden sind, wenn diese Gegenstände die Sicherheit von Menschen, die Sittlichkeit oder die öffentliche Ordnung gefährden. Die einzuziehenden Gegenstände müssen einen Bezug zu einer Straftat (Anlasstat) aufweisen, indem sie zur Begehung der Straftat gedient haben oder bestimmt waren (Tatwerkzeuge) oder durch die Straftat hervorgebracht worden sind. Zusätzlich wird eine konkrete künftige Gefährdung verlangt. Das Gericht hat insoweit im Sinne einer Gefährdungsprognose zu prüfen, ob es hinreichend wahrscheinlich ist, dass der Gegenstand in der Hand des Täters in der Zukunft die Sicherheit von Menschen, die Sittlichkeit oder die öffentliche Ordnung gefährdet (<ref-ruling> E. 3.3.1 S. 149 mit Hinweis).
3.2 Die Vorinstanz begründet die Einziehung damit, dass am Drogenhandel beteiligte Personen notorischerweise Mobiltelefone benötigen würden, um Drogengeschäfte zu organisieren (angefochtenes Urteil E. 3.1 S. 30). Es kann offen gelassen werden, ob die Vorinstanz damit lediglich die Eignung von Mobiltelefonen für die Abwicklung von Drogenverkäufen darlegt oder sinngemäss feststellt, dass der Beschwerdeführer die Mobiltelefone tatsächlich dafür benützt hat. Da sich die Vorinstanz nicht zur Frage äussert, ob die Mobiltelefone eine konkrete künftige Gefährdung im Sinne von <ref-law> darstellen, verletzt sie ihre Begründungspflicht nach <ref-law>. Zudem hat das Bundesgericht selbst bei gegebenen Einziehungsvoraussetzungen hinsichtlich elektronischer Datenträger (so etwa Digitalkameras und Notebooks) erwogen, das Prinzip der Subsidiarität gebiete es, einzig die deliktischen Daten auf Kosten des Beschwerdeführers unwiederherstellbar zu löschen und diesem anschliessend die Datenträger samt Kopien der darauf enthaltenen legalen Daten wieder zurückzugeben (vgl. Urteil 6B_748/2008 vom 16. Februar 2009 E. 4.5.3 mit Hinweisen). Die Einziehung der drei Mobiltelefone verletzt somit Bundesrecht.
4. Die Beschwerde ist gutzuheissen. Der angefochtene Entscheid ist aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen (<ref-law>). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos. Es sind keine Gerichtskosten zu erheben (<ref-law>). Die Schweizerische Eidgenossenschaft (Bundesanwaltschaft) hat dem Beschwerdeführer dessen Parteikosten zu ersetzen (<ref-law>). Die Entschädigung ist dem Vertreter des Beschwerdeführers zuzusprechen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Bundesstrafgerichts vom 8. Januar 2009 aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird als gegenstandslos abgeschrieben.
3. Es werden keine Gerichtskosten erhoben.
4. Die Schweizerische Eidgenossenschaft (Bundesanwaltschaft) hat den Vertreter des Beschwerdeführers, Rechtsanwalt Hans Ludwig Müller, mit Fr. 3'000.-- zu entschädigen.
5. Dieses Urteil wird den Parteien und dem Bundesstrafgericht, Strafkammer, schriftlich mitgeteilt.
Lausanne, 31. Mai 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Koch