Client zur Domäne hinzufügen

Hallo zusammen,

ich habe folgendes Problem:

Der Computername eines Client in einer Windows Server 2003 Umgebung wurde dummerweise gelöscht, wodurch ich mich nicht mehr mit dem Client (Win XP) unter der Domäne anmelden kann.

Normalerweise würde ich mich jetzt lokal anmelden und den Pc wieder an die Domäne einbinden so dass auch im Active Directory der Computer wieder auftaucht - ABER:

Ich bekomme immer wieder die Meldung: Es wurde ein Konto für diesen Computer in der Domäne "xyz." gefunden. Möchten Sie dieses Konto verwenden? JA oder NEIN ?

Also schnell JA geklickt und zu aller Überraschung erhalte ich dann die MItteilung: Der Computer konnte nicht in die Domäne eingebunden werden, da der folgende Fehler aufgetreten ist: "Zugriff verweigert"

Ich hab alles 1000mal gescheckt, alle einstellungen scheinen korrekt zu sein. Hat vielleicht jemand von Euch eine Idee? Bin für jeden Hinweis dankbar.
( Server: WIN2003 - Client: XP )

Dankeschön,
Oliver