ok a couple more things i'd check -
is the backup exec running with admin cred's of the other machine?
check the firewall exceptions or just turn it off to test first.
Check antivirus is not blocking any jobs running in the background
check for any BE updates (Tools>liveupdate)
Sorry - just re-read the 'did stop DNS service over move' - have you restarted DNS? Backup Exec will rely on DNS as it browses servers by server name.
if you have restarted DNS and it's still not picking up you need to change the pointer record of the backed up server name to the new IP address of the backed up server, or disjoin and rejoin the domain so it does it for you