Office 365/2013 Errors 30134-4 and 12007-4

We had a machine this morning that was being switched from a Office 2010 Home & Business PKC install to Office 2013 (via an Office 365 Midsize Business subscription). After uninstalling Office and rebooting the PC, the click to run installer for 2013 wouldn’t run – it was throwing error 12007-4. After some initial research, we ran the Microsoft Fix It tool for fully uninstalling Office, then ran Ccleaner to pick up any remaining pieces in the registry, and rebooted again.

After trying to run the installer this time, we got an error 30134-4, which we were unable to find any references to online. After some trial and error, this appears to be some related to some sort of DNS resolution issue – everything else was working fine network-wise, with the exception of this installer. Upon temporarily changing the DNS to Google (8.8.8.8 and 8.8.4.4), the Office installation went off without a hitch, and reverting back to the original DNS servers didn’t cause a problem afterwards.