Sachverhalt: A. Beamte der griechischen Polizei haben am 26. April 2000 Areal und Räumlichkeiten der Unternehmungen A._ und B._ in Z._ (Korinth) durchsucht. Dabei sollen sie ein illegales und zur Herstellung synthetischer Betäubungsmittel und deren Ausgangsstoffe geeignetes Laboratorium entdeckt haben, welches in jenem Zeitpunkt in Betrieb war und in welchem rund 21'000 Amphetamintabletten sichergestellt worden sein sollen. Eigentümerin des Laboratoriums soll nach Angaben von C._ die seinem Bruder X._ gehörende B._ gewesen sein. In der Folge eröffneten die griechischen Strafverfolgungsbehörden gegen X._ und weitere Beteiligte eine Hauptuntersuchung unter anderem wegen gemeinsamer Herstellung von Amphetaminen sowie wegen gemeinsamen Schmuggels und Imports ohne schriftliche Bewilligung des Laboratoriums. Später wurde eine weitere Hauptuntersuchung wegen Exports (mit dem Ziel des Verkaufs) von Betäubungsmitteln in Mittäterschaft sowie wegen unmittelbarer Mitwirkung bei dieser Handlung angeordnet. Gegen den landesabwesenden X._ erging am 4. Mai 2000 ein internationaler Haftbefehl. Am 26. Juni 2001 sprach das Appellationsgericht Nafplio die neben X._ ebenfalls angeklagten C._, D._, E._ sowie G._ der gewerbsmässigen Herstellung von Amphetaminen schuldig. Dabei ging es davon aus, dass die Verurteilten in Mittäterschaft mit X._ gehandelt haben. Das Gerichtsverfahren in Bezug auf Letzteren war am 22. März 2001 in Erwartung seiner Festnahme sistiert worden. B. Weil X._ als Schweizerbürger nicht an Griechenland ausgeliefert werden konnte, stellte das griechische Justizministerium ein Gesuch gemäss Art. 6 Abs. 2 in Verbindung mit Art. 12 des Europäischen Auslieferungsübereinkommens vom 13. Dezember 1957 (SR 0.353.1) um gerichtliche Verfolgung von X._. Die Anklagekammer des Kantons Bern kam diesem Ersuchen mit Beschluss vom 31. Oktober 2001 nach und wies die Akten dem Untersuchungsrichteramt III Bern-Mittelland zur weiteren Bearbeitung zu. Gestützt auf einen Bericht des Untersuchungsrichters unterbreitete indessen der Generalprokurator des Kantons Bern am 20. Februar 2002 die Akten der Bundesanwaltschaft, wobei er ausführte, die in Frage kommenden Delikte würden unter die organisierte Kriminalität fallen und seien zu einem wesentlichen Teil im Ausland begangen worden, weshalb Bundeszuständigkeit gegeben sei. Der Bundesanwalt verneinte diese jedoch zunächst, erklärte sich aber am 22. April 2002 dennoch bereit, das Verfahren zu übernehmen. In der Folge eröffnete die Schweizerische Bundesanwaltschaft am 5. Juli 2002 ein gerichtspolizeiliches Ermittlungsverfahren gegen X._ wegen gewerbs- und bandenmässig begangener Widerhandlungen gegen das Betäubungsmittelgesetz im Sinne von Art. 19 Ziff. 2 lit. b und c. Auf Antrag der Schweizerischen Bundesanwaltschaft eröffnete sodann das Eidgenössische Untersuchungsrichteramt eine Voruntersuchung wegen Verdachts der Widerhandlungen gegen das Betäubungsmittelgesetz, qualifiziert begangen ab ca. 1998 in Griechenland und anderswo, sowie wegen Anstiftung zu falschem Zeugnis, mehrfach begangen im Jahr 2003 in Bern und anderswo. C. Am 13. Juli 2005 erhob die Schweizerische Bundesanwaltschaft beim Bundesstrafgericht Anklage gegen X._ wegen qualifizierter Widerhandlungen gegen die Betäubungsmittelgesetzgebung sowie wegen Anstiftung zu falschem Zeugnis. Mit Entscheid vom 22. September/25. Oktober 2005 trat indessen das Bundesstrafgericht auf die Anklage nicht ein. Zur Begründung führte es im Wesentlichen aus, nach dem Wortlaut von Art. 340bis Abs. 1 lit. a StGB unterlägen der Bundesgerichtsbarkeit - soweit hier interessierend - einzig die von einer kriminellen Organisation im Sinne von Art. 260ter StGB ausgehenden Verbrechen. Die Beteiligung an einer solchen werde dem Angeklagten aber nicht zur Last gelegt, und aus der Anklageschrift gehe auch nicht hervor, dass die Verbrechen von einer solchen Organisation ausgegangen seien. Was die Anklage wegen Anstiftung zu falschem Zeugnis betreffe, beziehe sich diese Tat auf in Griechenland rechtshilfeweise auf schweizerisches Begehren einvernommene Zeugen, weshalb sie sich nicht, wie dies gemäss Art. 340 Ziff. 1 al. 7 StGB für Bundesgerichtsbarkeit erforderlich wäre, gegen eine Behörde des Bundes, sondern gegen eine ausländische Behörde richte. D. Gegen diesen Nichteintretensentscheid des Bundesstrafgerichts hat die Schweizerische Bundesanwaltschaft am 28. November 2005 Nichtigkeitsbeschwerde an den Kassationshof des Bundesgerichts eingereicht. Sie beantragt, den angefochtenen Entscheid aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen, eventuell die Strafkammer des Bundesstrafgerichts für die Beurteilung der Sache zuständig zu erklären. In seiner Vernehmlassung vom 21. Februar 2006 beantragt der Generalprokurator des Kantons Bern, die Nichtigkeitsbeschwerde gutzuheissen, während X._ mit Eingabe vom 10. März 2006 auf Abweisung schliesst. Das Bundesstrafgericht hat auf Gegenbemerkungen verzichtet. 