Sachverhalt: A. Die Schweizerische Eidgenossenschaft, der Kanton Tessin und die Gemeinde Muralto erliessen durch das Ufficio esazione e condoni des Kantons am 21. Januar 2004 gegenüber X._, Monaco, gestützt auf Sicherstellungsverfügungen drei Arrestbefehle (Nrn. 1, 2, 3) für Steuerforderungen im Umfang von insgesamt über 33 Mio. Franken. In den Arrestbefehlen wurden die Arrestgegenstände wie folgt bezeichnet: "Bei der Bank Z._, 7500 St. Moritz, alle Guthaben des Arrestschuldners; insbesondere Kontoguthaben, Wertschriften, Edelmetalle, Treuhanddepots, Safe-Inhalte, die auf den Namen des Schuldners oder auf den Namen von Frau Y._, gestorben am 20.03.2003, lauten; wie auch jeden Wert, keinen ausgeschlossen, welcher entweder auf den Namen des Schuldners oder auf den Namen von Frau Y._ eingetragen und/oder in dessen Eigentum ist oder bei dem der Schuldner oder Frau Y._ als Wirtschaftsberechtigter sich erweist. Insbesondere das Konto A._, das Konto n. 4 und das Konto n. 5. Alles soweit verarrestierbar, bis zur Deckung der Arrestforderung nebst Zinsen und Kosten." Das Betreibungsamt Oberengadin vollzog die Arreste am 22. Januar 2004 gemäss Arrestbefehlen und nannte als Arrestgegenstände - in wörtlicher Wiederholung der Angaben in den Arrestbefehlen - auch jeden Vermögenswert bei der Bank Z._ in St. Moritz, bei dem sich "der Schuldner oder Frau Y._ als [wirtschaftlich berechtigt] erweist". Hiergegen erhob die Bank Z._ Beschwerde mit dem Begehren, die Arreste seien insoweit aufzuheben, als die Arrestlegung auf allfällige Vermögenswerte und Guthaben angeordnet worden sei, bei denen X._ und/oder Y._ als wirtschaftlich Berechtigte erscheinen. B. Der Kantonsgerichtsausschuss von Graubünden als Aufsichtsbehörde über Schuldbetreibung und Konkurs hiess die Beschwerde mit Entscheid vom 16. März 2004 gut und hob den Arrestvollzug des Betreibungsamtes insoweit auf, als er sich auf Vermögenswerte bei der Bank Z._ in St. Moritz bezieht, welche nicht auf den Namen von X._ oder Y._ lauten, sondern diese lediglich daran wirtschaftlich Berechtigte sein sollen. C. Die Schweizerische Eidgenossenschaft, der Kanton Tessin und die Gemeinde Muralto haben den Entscheid der kantonalen Aufsichtsbehörde mit Beschwerdeschrift vom 1. April 2004 (rechtzeitig) an die Schuldbetreibungs- und Konkurskammer des Bundesgerichts weitergezogen und beantragen die Aufhebung des angefochtenen Entscheides und die Bestätigung des Arrestvollzuges des Betreibungsamtes. Die Aufsichtsbehörde schliesst ohne Gegenbemerkungen (Art. 80 OG) auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Bank Z._ als Beschwerdegegnerin beantragt ebenfalls die Abweisung. Weitere Vernehmlassungen sind nicht eingeholt worden.