Running through the whole setup procedure will produce a different machine security ID compared to the old box. AD wouldn't recognize it as the old machine if the name has been changed as well. OTOH, if some type of imaging was used, then it may be getting confused if the SID wasn't changed.
What I don't know is what will happen if there are duplicated SID's in play and you try to remove one from the domain (i.e. the duplicates may start to show problems as well.)