Faits: A. Le 17 septembre 2003, le Parquet général de la Fédération de Russie a remis aux autorités suisses une demande d'entraide établie le 15 août 2003 par le juge d'instruction chargé des affaires de grande importance auprès du Parquet général, Salavat Kounakbaéivitch Karimov. Fondée sur la Convention européenne d'entraide judiciaire en matière pénale (CEEJ; RS 0.351.1), conclue à Strasbourg le 20 avril 1959 et entrée en vigueur le 20 mars 1967 pour la Suisse et le 9 mars 2000 pour la Russie, la demande était présentée pour les besoins de la procédure pénale ouverte contre le ressortissant russe G._, des chefs d'escroquerie, d'abus de confiance et d'insoumission à une décision judiciaire, commis dans le cadre d'un groupe organisé. En tant que dirigeant de la banque Menatep (ci-après: Menatep), G._ se serait, avec l'aide de Platon Leonidovitch Lebedev, approprié frauduleusement un lot d'actions du capital de la société A._, au détriment de l'Etat, afin de prendre le contrôle de la société. G._ aurait refusé de se soumettre à l'injonction judiciaire de restituer le lot d'actions en question. Entre 1994 et 2002, il aurait organisé avec ses comparses la vente, par A._ et des intermédiaires, de grandes quantités de concentré d'apatite (phosphate de calcium utilisé comme engrais) aux sociétés suisses F._ et O._, à un prix inférieur à celui du marché (de l'ordre de 30 USD par tonne métrique). F._ et O._ auraient revendu l'apatite à l'étranger, au prix du marché (de l'ordre de 40 à 78 USD par tonne métrique). Les autorités requérantes soupçonnaient que les fonds ainsi détournés avaient été blanchis en Suisse. La demande tendait à la remise de la documentation concernant F._ et O._, à l'audition de leurs dirigeants, à la saisie et à la remise de la documentation bancaire relative aux opérations décrites, ainsi qu'à la détermination du sort des fonds. Le 31 octobre 2003, l'Office fédéral de la justice (ci-après: l'Office fédéral) a délégué au Ministère public de la Confédération l'exécution de la demande, laquelle a été complétée à plusieurs reprises. Le 14 novembre 2003, le Parquet général de la Fédération de Russie a précisé qu'était aussi impliqué dans le blanchiment des fonds Mikhail Borissovitch Khodorkovski, fondateur du groupe Menatep. Celui-ci détenait la totalité du capital-actions de plusieurs sociétés mêlées à l'affaire, dont E._. Il était signalé également que Menatep était titulaire de différents comptes bancaires, à Genève et Zurich. Selon le complément du 18 novembre 2003, Khodorkovski avait été inculpé, dans le même contexte de faits, pour escroquerie, abus de confiance, insoumission à une décision judiciaire, appropriation, soustraction d'impôt et faux dans les titres, commis dans le cadre d'un groupe organisé. Khodorkovski aurait dirigé l'opération consistant à mettre la main sur le capital de A._, ainsi que les ventes à F._ et O._. Avec Lebedev, Khodorkovski aurait obtenu frauduleusement des subventions pour un montant total de 407'120'540,28 RUR. Pour le blanchiment des fonds provenant des opérations délictueuses mises à la charge des prévenus, ceux-ci se seraient servis de sociétés dépendant de Menatep, parmi lesquelles Yukos Universal Ltd (ci-après: Yukos), active dans la production et le commerce du pétrole. La demande tendait à la saisie de la documentation relative à plusieurs comptes détenus par les différentes sociétés contrôlées par Menatep et Yukos, dont E._, ainsi que par les personnes physiques associées aux affaires de Khodorkovski. Le 12 mars 2004, l'autorité requérante a demandé qu'un représentant du Parquet général soit autorisé à participer à l'exécution des actes d'entraide. Elle a également produit une ordonnance rendue le 12 mars 2004 par le juge du district de Basmany de la ville de Moscou. Des actions civiles avaient été formées devant ce tribunal pour obtenir de Khodorkovski et consorts le paiement d'un montant total de 127'000'000'000 RUR, en relation avec l'appropriation des actions de A._. A titre de garanties, le juge a ordonné la saisie des fonds déposés sur tous les comptes détenus par les prévenus et les sociétés impliquées, dont E._, ainsi que par plusieurs tiers, auprès de divers établissements bancaires en Suisse. Selon le complément du 19 mars 2004, Yukos aurait vendu à des sociétés qu'elle contrôlait du pétrole et des produits dérivés à des prix inférieurs à celui du marché. Les destinataires auraient revendu ces produits à leur véritable prix. Le butin, correspondant à la différence de prix, aurait été blanchi en Suisse. Au complément était jointe une décision rendue le 18 mars 2004 par le juge du district de Basmany, ordonnant le séquestre de comptes ouverts en Suisse, pour les besoins de la procédure pénale en cours. Ce complément mentionne que E._ aurait servi au blanchiment du produit des délits mis à la charge de Khodorkovski et de ses comparses. Le 25 mars 2004, le Ministère public a rendu une décision d'entrée en matière ordonnant le séquestre d'un montant équivalent à 2'244'179'505.14 CHF déposé sur le compte n° g ouvert au nom de E._ auprès de la banque U._. B. Agissant par la voie du recours de droit administratif, E._ demande au Tribunal fédéral d'ordonner la levée du séquestre. Elle invoque l'art. 80e de la loi fédérale sur l'entraide internationale en matière pénale, du 20 mars 1981 (EIMP; RS 351.1), ainsi que le principe de la proportionnalité. Le Ministère public conclut principalement au rejet du recours, subsidiairement à son rejet dans la mesure de sa recevabilité. L'Office fédéral propose de rejeter le recours dans la mesure où il est recevable. Invitée à répliquer, la recourante a maintenu ses conclusions. 