Yes I have a few ideas …
You cannot take a server offline and bring a new server on-line using the same name. The SID and GUID will not match in AD. You can do the following.
1. Demote the new server
2. Remove the new server from the domain.
3. Take the new server offline.
4. Reset the machine account in AD.
5. Bring the new server online.
6. Join the new server to the domain using the reset account.
7. DCPromo the machine again.
Follow these steps and it should work. If not repeat 1-3 then delete the machine account. Use ADSI edit to manually remove any metadata left from the old account. Wait for replication and the contimue with steps 5-7.
Let us know how it turns out.