My scripts were set up to use cached credentials, so I was not specifying the credentials in the command line. This would normally look like this:
msdeploy.exe -verb:sync -source:contentPath="C:\inetpub\wwwroot\site1\dir1\" -dest:contentPath=D:\webroot\site1\dir1\,computerName=mymachine,username=myuser,password=mypassword
However, my scripts need to deploy to a wide range of machines and domains; and are stored in TFS, which means storing personal credentials is not possible. So I chose to use cached credentials instead of specifying the credentials in plain text. This is implemented by using the Windows Credential Manager, accessed via the Control Panel.
If you connect to a remote share on a machine, or connect to the machine via Remote Desktop, and choose to save the credentials, Windows will add them to the list in Credential Manager.
You can also manually add/remove items from the Credential Manager list.
So, anyway, when the scripts started to fail after the AD move, I tried running the msdeploy command line with the username and password arguments. This worked! So all I had to do was manually remove the cached credentials from Credential Manager, and reconnect to each server's file shares.