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.

Das Bundesgericht zieht in Erwägung:
1. Das Bundesstrafgericht in Bellinzona ist das erstinstanzliche Strafgericht des Bundes (Art. 191a Abs. 1 BV; Art. 1 Abs. 1 des Bundesgesetzes über das Bundesstrafgericht, Strafgerichtsgesetz SGG; SR 173.71). Seine Strafkammer beurteilt Strafsachen, die nach den Artikeln 340 und 340bis StGB der Bundesstrafgerichtsbarkeit unterstehen, soweit der Bundesanwalt die Untersuchung und Beurteilung nicht den kantonalen Behörden übertragen hat (Art. 26 lit. a SGG). Die Entscheide der Strafkammer des Bundesstrafgerichts können beim Kassationshof des Bundesgerichts mit Nichtigkeitsbeschwerde angefochten werden (Art. 1 Abs. 2 und Art. 33 Abs. 3 lit. b SGG). Das Verfahren richtet sich nach den Art. 268 ff. BStP, wobei der Bundesanwalt zur Beschwerde berechtigt ist (Art. 33 Abs. 3 lit. b SGG).
Die Nichtigkeitsbeschwerde der Bundesanwaltschaft wird damit begründet, dass der Nichteintretensentscheid der Strafkammer des Bundesstrafgerichts eidgenössisches Recht verletze, was den zulässigen Rügegründen des Art. 269 Abs. 1 BStP entspricht. Fragen liesse sich indessen, ob die Nichtigkeitsbeschwerde ausgeschlossen ist, weil dem Streit ein Zuständigkeitskonflikt zu Grunde liegt. Tatsächlich haben der Kassationshof des Bundesgerichts und die frühere Anklagekammer stets an der Auffassung festgehalten, dass aArt. 264 BStP, wonach Gerichtsstandskonflikte von der Anklagekammer zu entscheiden waren, als Sonderbestimmung dem Art. 268 BStP vorging, was selbst dann galt, wenn ein kantonales Gericht seine Zuständigkeit verneinte (<ref-ruling>). Heute ist für die Entscheidung von Anständen zwischen den Kantonen, aber auch von Anständen zwischen Bund und Kantonen die Beschwerdekammer des Bundesstrafgerichts zuständig (Art. 279 und Art. 260 BStP), wobei die Beschwerde gegen solche Entscheide an das Bundesgericht ausgeschlossen ist (Art. 33 Abs. 3 lit. a SGG, e contrario). Wenngleich es somit dabei bleiben muss, dass Gerichtsstandskonflikte zwischen den Kantonen, aber auch Anstände zwischen den Strafverfolgungsbehörden von Bund und Kantonen definitiv durch die Beschwerdekammer des Bundesstrafgerichts entschieden werden, kann es sich nicht gleich verhalten, wenn es die Strafkammer des Bundesstrafgerichts ist, welche den Zuständigkeitskonflikt durch einen Nichteintretensentscheid auslöst. Es wäre nicht sachgerecht, wenn dieser Konflikt durch die andere Kammer desselben Gerichts geregelt werden müsste. Vielmehr muss in einem solchen Fall die Nichtigkeitsbeschwerde wegen Verletzung eidgenössischen Rechts zugelassen werden. Mithin ist auf die fristgerecht erhobene Beschwerde der Bundesanwaltschaft einzutreten.
2. Gemäss Art. 340bis StGB unterstehen der Bundesgerichtsbarkeit unter anderem die strafbaren Handlungen nach Art. 260ter StGB sowie die Verbrechen, die von einer kriminellen Organisation im Sinne dieser Bestimmung ausgehen, sofern die strafbaren Handlungen zu einem wesentlichen Teil im Ausland (lit. a) oder in mehreren Kantonen begangen wurden und dabei kein eindeutiger Schwerpunkt in einem Kanton besteht (lit. b). Die Bundesgerichtsbarkeit ist zwingend im Unterschied zu den in Art. 340bis Abs. 2 StGB genannten Verbrechen des zweiten und des elften Titels, wo die Eröffnung des Ermittlungsverfahrens durch die Bundesanwaltschaft die Bundesgerichtsbarkeit begründet (Abs. 3). Allerdings ändert der zwingende Charakter der Bundesgerichtsbarkeit nichts daran, dass diese in hohem Masse unbestimmt ist und nicht trennscharf bestimmt werden kann. Dies gilt nicht nur, was den Begehungsort, sondern auch was den Tatbestand der kriminellen Organisation selbst betrifft, wobei hinzukommt, dass die Eröffnung eines Verfahrens nach Art. 260ter StGB nicht Voraussetzung der Zuständigkeit ist, sondern es genügt, dass das Verbrechen von einer solchen Organisation ausgeht. Wie es sich damit verhält, kann vielfach zu Beginn einer Untersuchung nicht mit Bestimmtheit festgestellt werden.
Gleich wie bei der Bestimmung des interkantonalen Gerichtsstandes, sind auch die Strafverfolgungsbehörden des Bundes und der Kantone gehalten, sich über die Zuständigkeit zu verständigen. Erst wenn eine solche Verständigung scheitert, liegt ein Kompetenzkonflikt vor, und unterbreitet die Strafverfolgungsbehörde, die zuerst mit dem Fall befasst war, die Angelegenheit der Beschwerdekammer des Bundesstrafgerichts (Art. 279 Abs. 1 BStP; Schweri/Bänziger, Interkantonale Gerichtsstandsbestimmung in Strafsachen, 2. Aufl., Bern 2004, Rz. 561 ff.). Kommt es demgegenüber zu einer Einigung, so kann der Beschuldigte an die Beschwerdekammer des Bundesstrafgerichts gelangen (Art. 279 Abs. 2 BStP i.V.m. Art. 214 Abs. 2 BStP; vgl. <ref-ruling> E. 2.3), was er hier aber nicht getan hat.
Nach der Rechtsprechung ist eine nachträgliche Änderung der einmal vereinbarten Zuständigkeit zwar grundsätzlich möglich, es bedarf dafür aber triftiger Gründe (<ref-ruling> E. 3a S. 286; <ref-ruling> E. 1; 71 IV 60 E. 1). Das ergibt sich namentlich bei fortgeschrittener Untersuchung bereits daraus, dass Gründe der Effizienz und der beschleunigten Durchführung des Verfahrens gegen eine solche Änderung sprechen (<ref-ruling> E. 2.4; <ref-ruling> E. 3.5; <ref-ruling> E. 3b S. 286). Die Strafkammer des Bundesstrafgerichts wird daher eine Vereinbarung zwischen den eidgenössischen und kantonalen Strafverfolgungsbehörden über die Zuständigkeit nur in Frage stellen dürfen, wenn diese auf einem eigentlichen Missbrauch des Ermessens beruht (<ref-ruling> E. 3a S. 286; <ref-ruling> E. 3c; <ref-ruling> E. 4a).
Nach diesem Massstab hatte die Strafkammer des Bundesstrafgerichts keinen Anlass, die Bundesgerichtsbarkeit in Frage zu stellen. Wohl trifft zu, dass die Bundesanwaltschaft zunächst ihre Zuständigkeit verneinte und auch nach Übernahme des Falles noch erklärte, sie würde die rechtlichen Überlegungen des Generalprokurators des Kantons Bern nicht integral anerkennen (act. 2, Beilage 5c). Dieser hatte ausgeführt, Hintergrund der Straftaten sei eine grössere Organisation von Griechen, welche eines der grössten Labors zur Herstellung von Amphetamintabletten betrieben. Verwiesen wurde weiter auf die erhebliche Bedeutung des Drogengeschäftes, auf den beachtlichen Organisationsgrad der Täterschaft und den multinationalen Kontext (Produktion in Griechenland, Export in Schiffsgeneratoren nach den Arabischen Emiraten, Transport und Verkauf in Westeuropa, Rückfluss des Gewinnes über verschiedene Finanzinstitute zurück nach Griechenland). Im Schlussbericht des Eidgenössischen Untersuchungsrichters wird ferner festgehalten, Gegenstand des Verfahrens sei eine arbeitsteilige und methodisch hoch professionelle Produktion von Amphetaminen, welche einerseits im Rahmen einer betrieblichen Hierarchie erfolgt sei, anderseits als illegaler Bereich in den legalen Produktionsbereich der A._ integriert und gleichzeitig abgeschottet gewesen sei. Zutritt zu den Räumlichkeiten hätten bloss die Beschuldigten als unmittelbar Mitwirkende gehabt, und Kontakte zwischen den Mitarbeitenden der A._ zu dem für die Produktion zuständigen D._ seien unterbunden worden. Die getätigte Investition des Kaufes eines Reaktors mache deutlich, dass die Produktion auf Dauer angelegt gewesen sei (act. 2, Beilage 4, S. 131). Bei dieser Ausgangslage kann jedenfalls nicht gesagt werden, es habe keinen sachlichen Hintergrund für die Annahme gegeben, die Straftaten seien von einer kriminellen Organisation ausgegangen. Dass der Bundesanwalt die rechtlichen Ausführungen des Generalprokurators nicht vollumfänglich teilen wollte, ändert hieran nichts. Vereinbarungen über die Zuständigkeit werden nicht selten trotz unterschiedlicher Auffassungen der beteiligten Strafverfolgungsbehörden geschlossen, was aber die Einigung nicht missbräuchlich erscheinen lässt. Erweist sich die Bejahung der Bundesgerichtsbarkeit demnach als haltbar, so hätte die Strafkammer des Bundesstrafgerichts auf die Anklage eintreten müssen.
3. Die Strafkammer des Bundesstrafgerichts verneint auch die Zuständigkeit für die Beurteilung der Anklage wegen Anstiftung zu falschem Zeugnis (Art. 307 StGB). Gemäss Art. 340 Ziff. 1 al. 7 StGB unterstehen der Bundesgerichtsbarkeit unter anderem die strafbaren Handlungen des 17. Titels, sofern sie gegen die Behörden des Bundes oder gegen die Bundesrechtspflege gerichtet sind. In Frage steht die Beeinflussung von Zeugen, welche auf Begehren der Strafverfolgungsbehörde des Bundes in Griechenland rechtshilfeweise einvernommen wurden. Für die Zuständigkeit kann es nur darauf ankommen, ob ein Verfahren der kantonalen Rechtspflege oder aber der Bundesrechtspflege betroffen ist. Da hier das zweite zutrifft, ist Bundesgerichtsbarkeit gegeben.
4. Die Nichtigkeitsbeschwerde ist damit gutzuheissen und die Sache an die Vorinstanz zurückzuweisen. Bei diesem Ausgang des Verfahrens hat der Beschwerdegegner, der die Abweisung der Beschwerde beantragt, die bundesgerichtlichen Kosten zu tragen.

Demnach erkennt das Bundesgericht:
1. Die Nichtigkeitsbeschwerde wird gutgeheissen, der Entscheid des Bundesstrafgerichts vom 22. September/25. Oktober 2005 aufgehoben, und die Sache wird an die Vorinstanz zurückgewiesen.
2. Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdegegner auferlegt.
3. Dieses Urteil wird den Parteien und dem Bundesstrafgericht, Strafkammer, sowie dem Generalprokurator des Kantons Bern schriftlich mitgeteilt.
Lausanne, 28. März 2006
Im Namen des Kassationshofes
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: