Hi Steven, when you say "The machine that is really slow to authenticate has a different Computer name than its DNS name on Active Directory Object" , what do you mean exactly ?
Indeed DNS and AD , Specially Sites and Services will be 2 good places to start looking for. Please provide more details
Also take a look at the DC you are authenticating with , if you have several sites you must review if you are pointing to a remote DC via Sites and Services.
Best regards, Andres.