In the end we used LDIFDE to do an AD search for duplicate SPN's (Service Principal Name) as some research we did indicated this could be an issue. As it turns out the old (renamed) server object still had an SPN registered to it containing the name we wanted to use. Removing the old object resolved the issue. I would imagine that just removing the specific SPN would resolve it as well if you needed the object.