Sachverhalt:
A. Die Schweizerische Bundesanwaltschaft führt seit 31. Januar 2002 eine Strafuntersuchung gegen X._ wegen Gehilfenschaft zu ungetreuer Geschäftsbesorgung, Beteiligung an einer kriminellen Organisation und Geldwäscherei. Die Strafuntersuchung stehe im Zusammenhang mit einem separaten Strafverfahren in Russland; die russische Strafjustiz habe die (russischen) Hauptangeschuldigten u.a. wegen Vermögensdelikten in Millionenhöhe zum Nachteil der Fluggesellschaft Aeroflot angeklagt. Die Bundesanwaltschaft wirft X._ vor, er habe die russischen Hauptangeschuldigten mit Hilfe von Gesellschaften, die von ihm kontrolliert worden seien, auf strafbare Weise unterstützt. Am 11. Juli 2003 beantragte die Bundesanwaltschaft die Eröffnung einer Voruntersuchung.
B. Am 22. Juli 2003 eröffnete die Eidgenössische Untersuchungsrichterin die Voruntersuchung. Mit Verfügung vom 23. Februar 2004 erliess sie eine Pass- und Schriftensperre gegen X._. Gleichzeitig verfügte sie gegen den Angeschuldigten eine Meldepflicht (wöchentliche Meldung bei der Kantonspolizei Bern). Die strafprozessualen Zwangsmassnahmen (Ersatzmassnahmen anstelle von Untersuchungshaft) wurden mit dem Bestehen von dringendem Tatverdacht und Fluchtgefahr begründet.
C. Gegen die Zwangsmassnahmenverfügung der Eidgenössischen Untersuchungsrichterin erhob X._ am 26. Februar 2004 Beschwerde bei der Anklagekammer des Bundesgerichtes. Er beantragte die Wiederaushändigung der eingezogenen Ausweispapiere sowie die Aufhebung der Ausreisesperre und der Meldepflicht. Nachdem die Anklagekammer des Bundesgerichtes per 31. März 2004 aufgelöst worden war, entschied zuständigkeitshalber das Bundesstrafgericht (Beschwerdekammer) über die hängige Beschwerde. Mit Entscheid vom 28. April 2004 hiess das Bundesstrafgericht die Beschwerde gut und hob die Verfügung der Eidgenössischen Untersuchungsrichterin vom 23. Februar 2004 auf.
D. Gegen den Entscheid des Bundesstrafgerichtes vom 28. April 2004 gelangte die Bundesanwaltschaft mit Beschwerde vom 2. Juni 2004 an das Bundesgericht. Sie rügt eine Verletzung ihrer prozessualen Parteirechte und beantragt die Aufhebung des angefochtenen Entscheides sowie die Rückweisung an das Bundesstrafgericht zur Neubeurteilung.
E. Das Bundesstrafgericht und X._ haben am 8. bzw. 10. Juni 2004 auf Vernehmlassungen je ausdrücklich verzichtet. Die Eidgenössische Untersuchungsrichterin schliesst in ihrer Stellungnahme vom 11. Juni 2004 sinngemäss auf Gutheissung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
1. Die Bundesanwaltschaft beanstandet zunächst, dass das Bundesstrafgericht ihr den angefochtenen Entscheid (trotz entsprechender Aufforderung durch das Eidgenössische Untersuchungsrichteramt vom 6. Mai 2004) nicht förmlich eröffnet und zugestellt habe. Auf separate Beschwerde des Angeschuldigten vom 6. Mai 2004 hin habe das Bundesstrafgericht die Eidgenössische Untersuchungsrichterin sodann mit Verfügung vom 17. Mai 2004 (während der laufenden Rechtsmittelfrist) angewiesen, den angefochtenen Entscheid unverzüglich zu vollziehen. Auch die Verfügung vom 17. Mai 2004 habe das Bundesstrafgericht der Bundesanwaltschaft nicht zugestellt. Ausserdem sei die Bundesanwaltschaft (trotz ihrer Parteistellung im Voruntersuchungsverfahren) im Beschwerdeverfahren vor dem Bundesstrafgericht nicht angehört bzw. zur Stellungnahme eingeladen worden. Neben der Verletzung von einschlägigen Verfahrensvorschriften rügt die Bundesanwaltschaft eine Missachtung des rechtlichen Gehörs bzw. ihrer Parteirechte im Beschwerdeverfahren vor dem Bundesstrafgericht.
2. Es fragt sich zunächst, ob in der vorliegenden Streitsache überhaupt der Beschwerdeweg ans Bundesgericht offen steht.
2.1 Art. 33 des Bundesgesetzes vom 4. Oktober 2002 über das Bundesstrafgericht (SGG, SR 173.71) ist seit 1. April 2004 in Kraft. Das Bundesstrafgericht übernimmt die Fälle, die bei Inkrafttreten des SGG vor der Anklagekammer des Bundesgerichtes hängig waren (Art. 33 Abs. 1 SGG). Hängige Fälle werden nach neuem Recht weitergeführt (Art. 33 Abs. 2 SGG). Bis zum Inkrafttreten der hängigen Totalrevision der Bundesrechtspflege (voraussichtlich im Jahr 2007) kann gegen die Entscheide der Beschwerdekammer des Bundesstrafgerichtes über Zwangsmassnahmen innert 30 Tagen seit der Eröffnung wegen Verletzung von Bundesrecht beim Bundesgericht Beschwerde geführt werden. Das Verfahren richtet sich sinngemäss nach den Art. 214-216, 218 und 219 BStP (Art. 33 Abs. 3 lit. a SGG).
2.2 Bei der hier streitigen Pass- und Schriftensperre sowie der Meldepflicht handelt es sich um strafprozessuale Zwangsmassnahmen (vgl. Robert Hauser/Erhard Schweri, Schweizerisches Strafprozessrecht, 5. Aufl., Basel 2002, § 68 Rz. 45; Niklaus Schmid, Strafprozessrecht, 4. Aufl., Zürich 2004, Rz. 717 ff.). Zwar geht es dabei um mildere Ersatzmassnahmen anstelle des Erlasses von Untersuchungshaft, mit denen (im Rahmen der Verhältnismässigkeit) einer gewissen Fluchtgefahr des Angeschuldigten vorgebeugt werden soll (vgl. Schmid, a.a.O., Rz. 717). Die Massnahmen führen jedoch zu einer empfindlichen Einschränkung der Bewegungsfreiheit (bzw. der persönlichen Freiheit und der Wirtschaftsfreiheit) des Betroffenen. Dies gilt besonders im hier zu beurteilenden Fall. Gemäss den vorliegenden Akten hat der Beschwerdegegner seinen Hauptwohnsitz auf Zypern. Es handelt sich bei ihm um einen selbstständig erwerbenden Geschäftsmann. Infolge der Pass- und Schriftensperre bzw. des Ausreiseverbots konnte er sich weder an seinen Hauptwohnsitz begeben, noch Geschäften im Ausland nachgehen oder aus privaten Motiven (Besuche, Urlaub usw.) reisen. Ausserdem wurde ihm die Verpflichtung auferlegt, sich wöchentlich bei der Berner Kantonspolizei zu melden.
Nach dem Gesagten ist die Beschwerde an das Bundesgericht in der vorliegenden Streitsache grundsätzlich zulässig.
3. Weiter ist zu prüfen, ob die Bundesanwaltschaft zur Beschwerde legitimiert ist, ob ihr die prozessualen Parteirechte zustehen und ob die Beschwerdefrist eingehalten wurde.
3.1 Gemäss Art. 33 Abs. 3 lit. a SGG ist Art. 214 Abs. 2 BStP hier sinngemäss anwendbar. Danach sind namentlich die Parteien zur Beschwerde legitimiert. Parteien im Bundesstrafverfahren sind der Beschuldigte, die Bundesanwaltschaft und (in gewissen Fällen) der Geschädigte (Art. 34 BStP). Der Bundesanwaltschaft stehen auch während der Voruntersuchung Parteirechte zu (vgl. Art. 108 Abs. 1, Art. 110 Abs. 1, Art. 111 f., 115 Abs. 1, Art. 116, 118 f. und 120 Abs. 1 BStP). Auch nach bisheriger Praxis der Anklagekammer des Bundesgerichtes (welche bis 31. März 2004 in den Beschwerdesachen nach Art. 214 ff. BStP zuständig war) wurde die Bundesanwaltschaft als Partei behandelt (vgl. z.B. Urteil 8G.7/2000 vom 20. April 2000; s. auch <ref-ruling> sowie Art. 76 Abs. 1 lit. b Ziff. 3 des Entwurfes zum Bundesgesetz über das Bundesgericht [E-BGG], BBl 2001 S. 4480 ff., 4498 f.).
Nach dem Gesagten ist die Bundesanwaltschaft als Vertreterin der Anklage mit Parteistellung zur Beschwerdeführung befugt. Es kann offen bleiben, ob die Bundesanwaltschaft ihre Beschwerdelegitimation in jenen Fällen verlieren würde, bei denen Streitgegenstand eine Verfügung ist, welche von der Bundesanwaltschaft selbst erlassen wurde (vgl. dazu Peter Bösch, Die Anklagekammer des Schweizerischen Bundesgerichts, Aufgaben und Verfahren, Diss. Zürich 1978, S. 71). Im vorliegenden Fall wurden die streitigen Zwangsmassnahmen (im Sinne von Art. 214 Abs. 1 BStP) von der Eidgenössischen Untersuchungsrichterin im Voruntersuchungsverfahren verfügt.
3.2 In verfahrensrechtlicher Hinsicht beschwert sich die Bundesanwaltschaft zunächst darüber, dass das Bundesstrafgericht ihr den angefochtenen Entscheid sowie eine weitere Verfügung des Bundesstrafgerichtes vom 17. Mai 2004 nicht förmlich zugestellt habe. In der Verfügung vom 17. Mai 2004 sei die Eidgenössische Untersuchungsrichterin zudem angewiesen worden, den angefochtenen Entscheid "unverzüglich" (noch vor Ablauf der Rechtsmittelfrist) zu vollziehen.
3.3 Laut Verteiler wurde der angefochtene Entscheid nur dem Angeschuldigten sowie der Eidgenössischen Untersuchungsrichterin mitgeteilt. Die Beschwerdeentscheide des Bundesstrafgerichtes betreffend strafprozessuale Zwangsmassnahmen im Bundesstrafverfahren sind jedoch auch der Bundesanwaltschaft zu eröffnen, da diese, wie dargelegt, Parteistellung hat und zur Ergreifung von Rechtsmitteln legitimiert ist (Art. 34 BStP; Art. 214 Abs. 2 BStP i.V.m. Art. 33 Abs. 3 lit. a SGG).
3.4 Wie sich aus den Akten weiter ergibt, hat das Bundesstrafgericht (Beschwerdekammer) die Eidgenössische Untersuchungsrichterin mit Erkenntnis vom 17. Mai 2004 angewiesen, den - vorliegend angefochtenen - Entscheid des Bundesstrafgerichtes vom 28. April 2004 "unverzüglich zu vollziehen". Anderseits wird in der Rechtsmittelbelehrung des angefochtenen Entscheides (mit Recht) darauf hingewiesen, dass dagegen "innert 30 Tagen seit der Eröffnung" die Beschwerde beim Bundesgericht zulässig ist (vgl. Art. 33 Abs. 3 lit. a SGG). Aus dem angefochtenen Entscheid geht nicht hervor, wann dieser den Parteien mitgeteilt wurde. Nach unwidersprochener Darstellung der Bundesanwaltschaft wurde ihr der angefochtene Entscheid am 3. Mai 2004 indirekt (durch die Eidgenössische Untersuchungsrichterin) zugestellt.
Gemäss den vorliegenden Akten wurde der angefochtene Entscheid der Bundesanwaltschaft frühestens am 3. Mai 2004 (indirekt) eröffnet. Mit Posteingang der Beschwerde beim Bundesgericht am 3. Juni 2004 wurde die 30-tägige Beschwerdefrist gewahrt (vgl. Art. 32 OG i.V.m. Art. 99 Abs. 1 BStP).
3.5 Die Beschwerde der Bundesanwaltschaft ist in französischer Sprache abgefasst. Der Beschwerdegegner und sein Anwalt sind (nach den vorliegenden Akten zu schliessen) deutscher Muttersprache. Der Beschwerdegegner hält sich in Bern auf bzw. wird in der streitigen Verfügung der Untersuchungsrichterin verpflichtet, sich wöchentlich bei der Berner Kantonspolizei zu melden. Der angefochtene Entscheid des Bundesstrafgerichtes erging auf deutsch. Daher ist auch das vorliegende Beschwerdeverfahren grundsätzlich auf deutsch zu instruieren (vgl. Art. 37 Abs. 3 OG). In Fällen wie dem vorliegenden könnte erwartet werden, dass auch die Bundesanwaltschaft ihre Prozesseingaben künftig in der Sprache des angefochtenen Entscheides (hier: deutsch) einreicht.
4. Die Bundesanwaltschaft rügt eine Verletzung des rechtlichen Gehörs bzw. ihrer prozessualen Parteirechte im Beschwerdeverfahren vor dem Bundesstrafgericht.
4.1 Wie sich aus den Akten und den obigen Erwägungen zusammenfassend ergibt, erfolgte trotz gesetzlicher Parteistellung der Bundesanwaltschaft keine Einladung an diese zur Vernehmlassung und keine förmliche Eröffnung des angefochtenen Entscheides und der (den sofortigen Vollzug anordnenden) Verfügung vom 17. Mai 2004 gegenüber der Bundesanwaltschaft. Mit Schreiben vom 6. Mai 2004 hatte die Eidgenössische Untersuchungsrichterin das Bundesstrafgericht darauf hingewiesen, dass der Bundesanwaltschaft Parteistellung zukomme und diese zur allfälligen Ergreifung von Rechtsmitteln gegen den angefochtenen Entscheid legitimiert sei. Die Untersuchungsrichterin lud das Bundesstrafgericht daher ein, den angefochtenen Entscheid der Bundesanwaltschaft förmlich zu eröffnen. Ausserdem kündigten die Untersuchungsrichterin und die Bundesanwaltschaft dem Bundesstrafgericht (mit Schreiben vom 6. bzw. 12. Mai 2004) die Einlegung eines Rechtsmittels mit Gesuch um aufschiebende Wirkung an (vgl. Art. 218 BStP). Unbestrittenermassen erfolgte dennoch keine Urteilszustellung an die Bundesanwaltschaft. Stattdessen wies das Bundesstrafgericht die Untersuchungsrichterin am 17. Mai 2004 (während der laufenden Rechtsmittelfrist) an, den angefochtenen Entscheid "unverzüglich zu vollziehen". Auch diese Verfügung wurde der Bundesanwaltschaft nicht eröffnet.
4.2 Insgesamt wurden die Parteirechte der Bundesanwaltschaft mehrmals verletzt. Wie erwähnt, wurde die Bundesanwaltschaft schon nach der früheren Praxis der Anklagekammer des Bundesgerichtes (auch bei Beschwerden gegen Amtshandlungen des eidgenössischen Untersuchungsrichteramtes) als Partei behandelt (vgl. auch Art. 76 Abs. 1 lit. b Ziff. 3 E-BGG). Insbesondere wurde die Bundesanwaltschaft regelmässig zur Vernehmlassung eingeladen, und es wurden ihr die Urteile der Anklagekammer förmlich mitgeteilt.
Im vorliegenden Fall rechtfertigt sich keine allfällige "Heilung" der Verfahrensfehler im Beschwerdeverfahren vor Bundesgericht, zumal dem Bundesgericht nur eine auf Rechtsfragen beschränkte Kognition zukommt (vgl. Art. 33 Abs. 3 lit. a SGG). Bei dieser Sachlage hat eine Rückweisung der Streitsache an das Bundesstrafgericht zu erfolgen, zur Neuentscheidung unter Wahrung der Parteirechte der Bundesanwaltschaft.
5. Zusammenfassend ergibt sich, dass die Beschwerde gutzuheissen und der angefochtene Entscheid aufzuheben ist. Die Streitsache ist an das Bundesstrafgericht zur Neubeurteilung im Sinne der vorstehenden Erwägungen zurückzuweisen (vgl. Art. 219 Abs. 2 BStP).
Nachdem Art. 219 Abs. 3 BStP durch Ziff. I/4 des Bundesgesetzes vom 19. Dezember 2003 über das Entlastungsprogramm 2003 (mit Wirkung seit 1. April 2004) aufgehoben worden ist (AS 2004 S. 1633, 1647; BBl 2003 S. 5615), richtet sich die Frage der Kostenfolgen im Verfahren vor Bundesgericht nach den allgemeinen Vorschriften des OG. Gemäss Art. 156 Abs. 1 OG werden die Gerichtskosten in der Regel der vor Bundesgericht unterliegenden Partei auferlegt. Aufgrund der besonderen Verhältnisse des vorliegenden Falles wird auf die Erhebung von Gerichtskosten verzichtet (vgl. auch Art. 156 Abs. 2 OG). Da der Beschwerdegegner sich am vorliegenden Verfahren nicht beteiligt (bzw. auf Vernehmlassung verzichtet) hat, ist über eine allfällige Parteientschädigung oder Kostenauflage an ihn nicht zu befinden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, und der angefochtene Entscheid des Bundesstrafgerichtes vom 28. April 2004 wird aufgehoben.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Parteien, dem Eidgenössischen Untersuchungsrichteramt, Untersuchungsrichterin Maria-Antonella Bino, sowie dem Bundesstrafgericht, Beschwerdekammer, schriftlich mitgeteilt.
Lausanne, 22. Juni 2004
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: