Sachverhalt:
A. Am 16. Juli 1998 erteilte die Baubehörde der Gemeinde Samnaun A._ eine nachträgliche Baubewilligung für einen Ladeneinbau im Untergeschoss der Liegenschaft Samnaun Parzelle Nr. 48. Am 4. November 1999 erteilte sie eine weitere Baubewilligung für die Umnutzung von Lager- und Geschäftsflächen im Untergeschoss zu Garagen und Verkaufsflächen.
Am 4. Februar 2003 reichte Y._, der Sohn von A._, erneut ein Baugesuch ein, welches verschiedene Umbaumassnahmen innerhalb der bestehenden Geschäftslokalitäten vorsah. Gegen das Gesuch erhob die X._ AG, Eigentümerin der benachbarten Parzelle Nr. 61, am 17. März 2003 Einsprache. Am 9. Mai 2003 wies die Baubehörde die Einsprache der X._ AG ab und erteilte die Baubewilligung.
B. Die X._ AG erhob dagegen am 27. Mai 2003 Rekurs an das Verwaltungsgericht des Kantons Graubünden, welches das Rechtsmittel mit Urteil vom 30. Juni 2004 abwies.
C. Die X._ AG erhob am 8. September 2004 staatsrechtliche Beschwerde mit dem Antrag, das Urteil des Verwaltungsgerichts aufzuheben. Zudem beantragte sie die Erteilung der aufschiebenden Wirkung.
D. Die Gemeinde Samnaun, das Verwaltungsgericht Graubünden sowie Y._ beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei.
E. Mit Verfügung des Präsidenten der I. öffentlichrechtlichen Abteilung des Bundesgerichts vom 4. Oktober 2004 wurde der Beschwerde die aufschiebende Wirkung erteilt.
F. In dem vom Bundesgericht angeordneten zweiten Schriftenwechsel halten die Parteien an ihren Rechtsbegehren fest.

Das Bundesgericht zieht in Erwägung:
1. Gegen den kantonal letztinstanzlichen, auf kantonales Recht gestützten Endentscheid ist grundsätzlich die staatsrechtliche Beschwerde zulässig (Art. 84 und 86 Abs. 1 OG). Die Beschwerdeführerin ist als Eigentümerin der benachbarten Parzelle legitimiert, mit staatsrechtlicher Beschwerde eine willkürliche Anwendung von Bauvorschriften zu rügen, die (auch) dem Schutz nachbarlicher Interessen dienen (Art. 88 OG; <ref-ruling> E. 2c S. 46). Dazu gehören Bestimmungen über die Ausnützungsziffern (<ref-ruling> E. 2d S. 47), deren willkürliche Anwendung die Beschwerdeführerin in erster Linie rügt.
2. 2.1 In der rechtskräftigen Baubewilligung vom 4. November 1999 hatte die Gemeinde festgestellt, dass für das damals bewilligte Einkaufszentrum des Beschwerdegegners eine Bruttogeschossfläche von 1'072.4 m2 anrechenbar sei. Bei der nun streitigen Baubewilligung ist die Gemeinde davon ausgegangen, eine Umnutzung, bei welcher die Bruttogeschossfläche nicht erhöht werde, sei auch dann zulässig, wenn die zulässige Ausnützung überschritten sei. Vorliegend beanspruche die umstrittene Umnutzung gegenüber der rechtskräftig bewilligten Baute keine zusätzliche Bruttogeschossfläche. Sie könne daher bewilligt werden, selbst wenn die frühere Baubewilligung zu Unrecht erteilt worden sein sollte.
2.2 Das Verwaltungsgericht hat erwogen, eine solche Praxis lasse sich aufgrund des einer Gemeinde zustehenden Ermessens- und Entscheidungsspielraumes ohne weiteres vertreten. Es hat sodann aufgrund der von der Gemeinde erstellten Zusammenstellung erwogen, rechtskräftig bewilligt seien 1'072.4 m2, mit den geplanten Nutzungsänderungen würden nur deren 1'064.5 beansprucht. Werde somit keine zusätzliche Bruttogeschossfläche beansprucht, so sei der Bauentscheid nicht zu beanstanden.
2.3 Die Beschwerdeführerin rügt zunächst als willkürlich, dass das Verwaltungsgericht die Praxis der Gemeinde als vertretbar und im Rahmen von deren Ermessens- und Beurteilungsspielraum betrachtet habe. Das Verwaltungsgericht habe damit auch eine formelle Rechtsverweigerung begangen, indem es seine Kognition in rechtswidriger Weise auf eine Willkürprüfung beschränkt habe.
Die vom Verwaltungsgericht geschützte Praxis der Gemeinde sei auch in der Sache willkürlich: Die frühere Baubewilligung habe keine Anordnung über die Anrechenbarkeit bestimmter Räume enthalten, so dass nicht von einer rechtskräftig bewilligten Nutzung die Rede sein könne. Die Rechtsauffassung der kantonalen Instanzen verstosse krass gegen die Art. 74 f. und 37 ff. des Baugesetzes der Gemeinde Samnaun vom 15. Juli 1985 (BG): Nach diesen Bestimmungen sei im Baubewilligungsverfahren in jedem Fall eine vollständige Berechnung der Ausnützungsziffer (AZ) einzureichen; es bestehe keine gesetzliche Grundlage für eine blosse Saldoberechnung. Die beanstandete Rechtsauffassung verstosse gegen die sonstige Praxis des Verwaltungsgerichts und führe zu Rechtsungleichheiten, namentlich auch im Verhältnis zu einem von der Beschwerdeführerin etwa zu gleicher Zeit eingereichten Bauprojekt, bei welchem die Behörde einen früher bewilligten AZ-Transport aberkannt habe (vgl. dazu den Bundesgerichtsentscheid vom heutigen Tag im Verfahren 1P.537/2004).
Sodann sei die Annahme des Verwaltungsgerichts willkürlich, wonach das Umbauvorhaben weniger Bruttogeschossfläche beanspruche als die bestehende Baute. Diese Beurteilung beruhe auf willkürlicher Ermittlung und Würdigung des Sachverhalts und auf einer willkürlichen Rechtsanwendung. In diesem Zusammenhang rügt die Beschwerdeführerin zudem eine Verletzung des rechtlichen Gehörs, indem das Verwaltungsgericht einen Beweisantrag betreffend Ermittlung des gewachsenen Terrains abgelehnt habe.
2.4 Das Bundesgericht überprüft im Verfahren der staatsrechtlichen Beschwerde die Anwendung kantonalen und kommunalen Rechts durch die kantonalen Behörden nur auf Willkür hin. Ein Entscheid ist willkürlich, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, auf einem offenkundigen Versehen beruht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Willkür liegt sodann nur vor, wenn nicht bloss die Begründung eines Entscheides, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 3.1 S. 178 mit Hinweisen).
3. Zu prüfen ist zunächst, ob es willkürlich ist, bei einem AZ-neutralen Vorhaben keinen umfassenden neuen AZ-Nachweis zu verlangen.
3.1 Wenn das Verwaltungsgericht im angefochtenen Urteil ausgeführt hat, die Praxis der Gemeinde lasse sich aufgrund des ihr zustehenden Ermessens- und Entscheidungsspielraumes ohne weiteres vertreten, so heisst das nicht, dass es seine Kognition in unzulässiger Weise auf eine Willkürprüfung reduziert hätte. Die Begriffe des Ermessens und des Entscheidungsspielraumes werden in Lehre und Rechtsprechung nicht immer in einer eindeutig definierten Weise verwendet. In der Sache hat das Verwaltungsgericht erwogen, dass den Gemeinden bei der Auslegung und Anwendung ihres eigenen Rechts ein gewisser Spielraum zustehe, in den das kantonale Gericht auch bei freier Rechtsprüfung nicht einzugreifen brauche.
Nach der bundesgerichtlichen Rechtsprechung besteht ein geschützter Beurteilungsspielraum der Gemeinde bei der Anwendung kommunalen Rechts in Zweifelsfällen, wenn die Auslegung schwierig ist und in besonderem Masse örtliche Verhältnisse zu würdigen sind (grundlegend <ref-ruling> E. 4 S. 373 f.; vgl. auch Entscheid P.194/1975 vom 6. Oktober 1976, publ. in ZBl 78/1977 S. 220, E. 4 mit Hinweisen). Im vorliegenden Fall ist streitig, ob und inwieweit bei Umbauvorhaben, die an sich keine zusätzliche Bruttogeschossfläche beanspruchen, ein Ausnützungsnachweis für das gesamte Grundstück erbracht werden muss. Diese Frage ist im kommunalen Baugesetz nicht ausdrücklich geregelt: Dieses kennt nur eine Regelung über den Wiederaufbau zerstörter oder abgebrochener Bauten im bisherigen Gebäudeumfang (Art. 6 BG), aber keine Bestimmung über die Änderung bestehender baugesetzwidriger Bauten. Da die Bündner Gemeinden im Bereich des Bauwesens autonom sind (<ref-ruling> E. 2b S. 8 mit Hinweisen), ist es in erster Linie Sache der Gemeinde zu beurteilen, ob ihr Baugesetz insoweit eine Lücke aufweist und wenn ja, wie diese Lücke zu füllen ist.
Bestand nach dem Gesagten ein Beurteilungsspielraum der Gemeinde musste sich das Verwaltungsgericht Zurückhaltung auferlegen. Es durfte deshalb die gemeindliche Praxis nur auf ihre Vertretbarkeit hin überprüfen, ohne eine formelle Rechtsverweigerung zu begehen.
3.2 Nach Art. 74 Abs. 1 lit. a und b BG ist u.a. für Umbauten und Änderungen der Zweckbestimmung bestehender Bauten und Räume eine Baubewilligung erforderlich. Nach Art. 75 Abs. 1 lit. h BG ist mit dem Baugesuch eine detaillierte Berechnung der Ausnützungsziffer einzureichen. Die Art. 37 ff. BG definieren sodann die Begriffe der Ausnützungsziffer, der anrechenbaren Geschossfläche und der anrechenbaren Grundstücksfläche. Die Auffassung der kantonalen Instanzen verstösst nicht gegen diese Bestimmungen: Es ist eine Baubewilligung eingeholt und in diesem Rahmen die Bruttogeschossfläche berechnet und überprüft worden. Umstritten ist in Wirklichkeit nicht die Pflicht zur Berechnung der Ausnützung, sondern die Tragweite der früher erteilten Baubewilligung.
Die Bestimmungen über die Ausnützung bezwecken eine Begrenzung der zulässigen Nutzung; ist eine Baute gestützt auf eine rechtskräftige Baubewilligung errichtet worden, so ist die damit bewilligte Nutzung formell rechtmässig, selbst wenn die Baubewilligung zu Unrecht eine zu hohe Ausnützung bewilligt haben sollte. Könnte somit die bewilligte Nutzung trotz ihrer allfälligen materiellen Rechtswidrigkeit beibehalten werden, so ist es nicht willkürlich, die bestehende Übernutzung auch dann zuzulassen, wenn anlässlich eines späteren Umbaus die Bruttogeschossfläche nicht vermehrt wird; denn das Ausmass der Rechtswidrigkeit wird gegenüber demjenigen Zustand, der ohnehin bestehen bleiben dürfte, nicht erhöht. Es verhält sich ähnlich, wie wenn ein rechtskräftig bewilligtes bestehendes Gebäude die geltenden Bestimmungen über die Gebäudemasse oder Grenzabstände nicht einhält: Es ist allgemein üblich, auch bei solchen Gebäuden innere Umbauten zuzulassen, ohne gleichzeitig eine Anpassung der Gebäudedimensionen an die Vorschriften zu verlangen.
Zwar schützt die bundesverfassungsrechtliche Bestandesgarantie nur die bestehende, nicht aber eine geänderte Nutzung, doch können die Kantone über diesen minimalen Schutz hinausgehen (<ref-ruling> E. 2a S. 122), was die meisten Kantone getan haben. Die Beschwerdeführerin vermag keine gesetzliche Bestimmung anzugeben, gegen welche die Praxis der Gemeinde verstossen soll. Es entsteht dadurch auch kein unhaltbares Ergebnis: Es wird bloss bei einem Umbau dasjenige Mass an Übernutzung beibehalten, das ohne Umbau ohnehin beibehalten werden dürfte. Dass eine Baute, die dem bestehenden Recht widerspricht, teilweise geändert, umgebaut oder gar erweitert werden kann, gilt sogar für zonenwidrige Bauten ausserhalb der Bauzone (Art. 24c Abs. 2 RPG) und ist erst recht innerhalb der Bauzone nicht unhaltbar, sondern im Gegenteil üblich.
3.3 Das Verwaltungsgericht ist auch nicht in Willkür verfallen, indem es im angefochtenen Entscheid angeblich von seiner bisherigen Praxis abgewichen sei, wonach aus einer falschen AZ-Berechnung in einem früheren Baubewilligungsverfahren keine verbindlichen Wirkungen für zukünftige Bauvorhaben abgeleitet werden können: Die von der Beschwerdeführerin erwähnten früheren Entscheide des Verwaltungsgerichts betreffen überwiegend Sachverhalte, in denen anlässlich eines Umbauvorhabens die Bruttogeschossfläche erweitert wurde. Dies ist eine andere Fragestellung als wenn die Bruttogeschossfläche nicht erhöht wird (vgl. dazu Entscheid 1P.537+561/2004 vom 6. Juni 2005 betreffend ein Bauvorhaben des Beschwerdeführers). Jedenfalls kann aufgrund der in den Akten liegenden Urteile nicht von einer feststehenden Praxis des Verwaltungsgerichts zur vorliegend streitigen Frage gesprochen werden, von der nur aus ernsthaften sachlichen Gründen abgewichen werden dürfte (<ref-ruling> E. 3c S. 52 mit Hinweis).
3.4 Die Beschwerdeführerin macht freilich geltend, die vorliegend angeblich AZ-neutrale Umnutzung sei in Wirklichkeit keineswegs irrelevant, da eine bestehende Wohnnutzung durch eine zusätzliche Ladennutzung ersetzt werde, was andere Auswirkungen auf die Umgebung habe. Indessen kennt das Baugesetz keine unterschiedlichen Nutzungsmasse für Wohn- und Gewerbenutzung. Es geht klarerweise davon aus, dass sich die Ausnützungsziffer unabhängig von der Art der Nutzung berechnet. Dann aber ist es nicht willkürlich, bei der Beurteilung, ob ein Bauvorhaben zusätzliche Ausnützung erfordert, nicht zwischen Wohn- und Ladennutzung zu differenzieren.
4. Zu prüfen ist weiter, ob das Verwaltungsgericht willkürlich angenommen hat, der Umbau beanspruche keine zusätzliche anrechenbare Geschossfläche.
4.1 Das Verwaltungsgericht ist aufgrund einer von der Gemeinde vorgenommenen Aufstellung zum Ergebnis gekommen, dass mit den geplanten Nutzungsänderungen eine Bruttogeschossfläche von lediglich 1'064.5 m2 realisiert werde, während rechtskräftig 1'072.4 m2 bewilligt seien. Die geplanten Änderungen würden daher sogar zu einer minimalen Reduktion der Bruttogeschossfläche führen.
Die Beschwerdeführerin kritisiert diese Berechnung in verschiedener Hinsicht: Einige der vom Verwaltungsgericht als bewilligt angenommenen Flächen seien bei der Bewilligung im Jahre 1999 gar nicht zur AZ hinzugerechnet worden. Sie könnten daher jetzt auch nicht in den AZ-Vergleich einbezogen werden.
4.2 Es erübrigt sich, im Detail zu prüfen, welche der beanstandeten Flächen anlässlich der früheren Baubewilligungen angerechnet worden sind. Das Verwaltungsgericht hat diesen Bruttogeschossfläche-Vergleich nämlich nur als Eventualerwägung für den Fall angestellt, dass in jedem Fall auch bei einem AZ-neutralen Umbau eine vollständige AZ-Berechnung zu verlangen wäre (E. 3a des angefochtenen Urteils). Primär ist es aber davon ausgegangen, dass ein solcher Vergleich gar nicht notwendig sei, wenn gegenüber dem bewilligten Zustand keine zusätzliche Ausnützung beansprucht werde (E. 2b des angefochtenen Urteils). Diese Überlegung ist - wie dargelegt - grundsätzlich verfassungsrechtlich nicht zu beanstanden.
Dies trifft auch dann zu, wenn mit der Beschwerdeführerin davon ausgegangen wird, das einige der eigentlich als anrechenbar zu betrachtenden Flächen früher fälschlicherweise nicht angerechnet worden sind: Diese Flächen wären aufgrund der Besitzstandsgarantie und der rechtskräftigen früheren Baubewilligungen so wie bewilligt nutzbar, selbst wenn dies aus heutiger Sicht materiell rechtswidrig sein sollte. Wird nun die anrechenbare Fläche gegenüber derjenigen Fläche reduziert, die zwar anrechenbar gewesen wäre, aber früher nicht angerechnet wurde, so wird durch den Umbau das Ausmass der Gesetzwidrigkeit reduziert. Es ist nicht willkürlich, anlässlich eines Umbaus nicht eine vollständige Beseitigung der Gesetzwidrigkeit zu verlangen, sondern sich mit deren Reduktion zu begnügen.
4.3 Es ist daher nur zu prüfen, ob das Verwaltungsgericht willkürlich angenommen hat, es werde gegenüber dem rechtskräftig bewilligten Zustand keine zusätzliche anrechenbare Bruttogeschossfläche beansprucht.
4.3.1 Die Dusche und das WC im 1. Untergeschoss wären anrechenbar gewesen und dürfen nach dem soeben Gesagten willkürfrei in den Vergleich einbezogen werden, selbst wenn sie (was in den Akten widersprüchlich behandelt wird) früher fälschlicherweise nicht angerechnet worden sein sollten.
4.3.2 Analoges gilt für das nördliche Lager im 1. UG, welches möglicherweise früher nicht angerechnet wurde, aber jedenfalls als Lager bewilligt war (vgl. Plan zur Baubewilligung von 1999, von der Gemeinde genehmigt mit Stempel vom 27. Oktober 1999). Dieses Lager wird nun durch den Abbruch der Mauer zum Gang mit diesem vereinigt. Das Verwaltungsgericht hat erwogen, dass das so erweiterte Lager nicht anzurechnen sei, weil es einerseits durch die rechtskräftige Baubewilligung abgedeckt sei und andererseits nach wie vor als Durchgang/Korridor zu nicht anrechenbaren Räumen im Nordtrakt diene.
Die Beschwerdeführerin kritisiert, durch den Abbruch der Mauer werde ein neues Lager geschaffen, welches mit dem bewilligten Zustand nicht identisch sei. Dieses neue Lager sei AZ-pflichtig. Dabei geht die Beschwerdeführerin irrtümlich davon aus (Beschwerde Ziff. 3.b S. 19 und Ziff. 4 S. 21), der vormalige Korridor umfasse 24.74 m2. Diese Fläche bezieht sich - wie aus dem Plan klar errechnet werden kann - auf die vereinigte Fläche des ehemaligen nördlichen Lagers und des ehemaligen Korridors. Das vorbestehende Lager von ca. 15-16 m2 ist als solches 1999 rechtskräftig bewilligt worden. Selbst wenn derjenige Teil des Korridors, der nun zum Lager geschlagen wird, entgegen der Annahme des Verwaltungsgerichts voll angerechnet wird, entsteht dadurch eine zusätzliche anrechenbare Fläche von höchstens ca. 9.5 m2 (vgl. Beilage 2 zur Vernehmlassung der Gemeinde vom 4. Oktober 2004).
Nach der Auffassung des Verwaltungsgerichts ist dieser Raum nicht anzurechnen, da er auch als Korridor zu nicht anrechenbaren Flächen dient. Selbst wenn dies als unhaltbar erachtet würde, weil der ehemalige Korridor nun teilweise auch als Lager genutzt werden kann, wäre es aber jedenfalls vertretbar, ihn nur teilweise anzurechnen. Bei zum Beispiel hälftiger Anrechnung ergäbe sich damit eine zusätzliche anrechenbare Fläche von knapp 5 m2.
4.3.3 Die Treppe vom 1. UG ins Freie und der Windfang im Obergeschoss sind rechtskräftig bewilligt und werden nicht verändert, so dass keine zusätzliche Bruttogeschossfläche gegenüber dem bewilligten Zustand errichtet wird. Dasselbe gilt für die grossen Lagerräume im Nordosttrakt: Diese wurden früher rechtskräftig bewilligt, ohne angerechnet zu werden. Selbst wenn dies rechtswidrig gewesen sein sollte, weil - wie die Beschwerdeführerin vorbringt - die Oberkante mehr als 1.2 Meter über das gewachsene Terrain hinausragt, können diese Räume aufgrund der gültigen Bewilligung weiterhin als Lager genutzt werden.
4.3.4 Das Verwaltungsgericht hat sodann angenommen, dass die Waschküche im Obergeschoss nicht angerechnet werden muss. Dies ist entgegen der Auffassung der Beschwerdeführerin nicht willkürlich, sondern entspricht im Gegenteil dem klaren Wortlaut von Art. 38 Abs. 2 lit. a BG.
4.3.5 Selbst wenn entgegen der Ansicht des Verwaltungsgerichts beim nördlichen Lager ca. 5 m2 zusätzlich angerechnet werden (vorne E. 4.3.2), wird per Saldo keine zusätzliche Bruttogeschossfläche geschaffen, da das Verwaltungsgericht von einer Abnahme der anrechenbaren Fläche von rund 8 m2 ausgegangen ist. Es ist deshalb jedenfalls im Ergebnis nicht willkürlich, wenn das Verwaltungsgericht davon ausgeht, die Umnutzung führe nicht zu einer zusätzlichen anrechenbaren Fläche. Dass allenfalls bei korrekter Berechnung heute die Ausnützung höher wäre als das zulässige Mass von 0.9, führt deshalb nicht dazu, dass die Umnutzung unzulässig wäre.
4.4 Auf der Grundlage dieser willkürfreien Betrachtung ist es unerheblich, ob die von der Beschwerdeführerin beanstandeten Lagerflächen unter- oder oberhalb der Schnittlinie von 1.2 Meter über dem gewachsenen Terrain liegen, da sie so oder anders rechtskräftig bewilligt sind (vorne E. 4.3.3). Das Verwaltungsgericht durfte daher den Beweisantrag der Beschwerdeführerin betreffend Ermittlung des gewachsenen und des aktuellen Terrains abweisen, ohne das rechtliche Gehör zu verletzen.
5. Die staatsrechtliche Beschwerde erweist sich damit als unbegründet. Bei diesem Ausgang des Verfahrens trägt die Beschwerdeführerin die Kosten des Verfahrens (Art. 156 Abs. 1 OG). Sie hat zudem dem Beschwerdegegner die Parteikosten zu ersetzen (Art. 159 Abs. 2 OG), ebenso der Gemeinde Samnaun, die als kleine Gemeinde ohne professionellen Rechtsdienst auf den Beizug eines Anwalts angewiesen war.

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen.
2. Die Gerichtsgebühr von Fr. 4'000.-- wird der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat den Beschwerdegegner und die Gemeinde Samnaun für das bundesgerichtliche Verfahren mit je Fr. 3'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Gemeinde Samnaun und dem Verwaltungsgericht des Kantons Graubünden, 4. Kammer, schriftlich mitgeteilt.
Lausanne, 6. Juni 2005
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin: