New Server Query AD is giving permission error
I would presume the server Adam service GUID changed and or need to create a new computer object for your (virtual) as it's associated with the physical (adsi).  

Presuming you've done all the user, machine creation. Perhaps run a com lime logo to confirm the ticket is valid database service and machine etc.? 

Objects in ADS is what I'd audit and confirm. 
Command kinit