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. 