Faits: A. En date du 14 juin 2004, l'établissement bancaire Y._ a déposé une plainte pénale auprès du Juge d'instruction du canton de Vaud, expliquant que le compte en banque de A._ auprès de Y._ à Curaçao, aux Antilles néerlandaises, avait été frauduleusement débité - apparemment au moyen d'un fax falsifié par un auteur inconnu - de trois montants pour un total de 660'000 USD et que cet argent avait été transféré illicitement sur un compte en banque ouvert au Portugal, à la B._, puis viré sur le compte de la société uruguayenne X._ SA auprès de la Compagnie Bancaire C._ SA, à Lausanne. Par décision des 14 et 16 juin 2004, le Juge d'instruction vaudois a bloqué, à concurrence de 660'000 USD, les avoirs détenus par la société X._ SA auprès de la Compagnie Bancaire C._ SA. Le magistrat instructeur vaudois a refusé une première fois de lever le séquestre par ordonnance du 15 juillet 2005, laquelle a été confirmée par le Tribunal d'accusation du Tribunal cantonal vaudois le 26 septembre 2005. Le 22 septembre 2006, la société X._ SA a formé une seconde demande de levée du séquestre pénal, que le Juge d'instruction vaudois a également rejetée par ordonnance du 26 septembre 2006. Le Tribunal d'accusation vaudois a confirmé celle-ci par arrêt du 7 novembre 2006. B. Par ordonnance du 4 juin 2008, le Juge d'instruction vaudois a levé le séquestre portant sur le compte de la société X._ SA auprès de la Compagnie Bancaire C._ SA, d'un montant de 660'000 USD, et ordonné la restitution de ce montant à la banque Y._. C. Par arrêt du 21 octobre 2008, le Tribunal d'accusation du Tribunal cantonal vaudois a rejeté le recours formé par la société X._ SA contre l'ordonnance du 4 juin 2008. D. Contre ce dernier arrêt, X._ SA dépose un recours en matière pénale devant le Tribunal fédéral. Elle conclut à l'annulation de l'arrêt attaqué et à la levée de la saisie pénale conservatoire qui frappe la relation bancaire n° 104'241 ouverte à son nom auprès de la Compagne Bancaire C._ SA. Appelée à se déterminer, Y._ conclut au rejet du recours. Dans le cas où l'ordre de restitution serait toutefois annulé, elle sollicite, à titre subsidiaire, le renvoi de la cause au juge d'instruction vaudois pour nouvelle décision sur les questions de la levée du séquestre et de la restitution des valeurs et, à titre plus subsidiaire, le maintien du séquestre jusqu'à droit connu sur le sort de l'action pénale. Le Ministère public vaudois a renoncé à déposer des déterminations. E. L'effet suspensif a été accordé par ordonnance du 13 janvier 2009.