Windows – Default Microsoft Windows Update Server

You could use PowerShell to update group policy. Here's an example:

set-gpregistryvalue -name "WU" -key HKLM\Software\Policies\Microsoft\Windows\WindowsUpdate -ValueName "WUServer", "WUStatusServer" -type String -Value "http://wsus01.internal.local:8530"

And here's where you can read up more on the amazingness that is powershell:

http://technet.microsoft.com/en-us/library/ee461027.aspx

OR AN EVEN BETTER ANSWER:

Step 1: Setup Active Directory
Step 2: Join computers to Active Directory domain
Step 3: Configure group policy to point computers to WSUS server
Step 4: Profit

It seems that this is due to the oddball GPO that my company uses.

As outlined here the GPO setting Computer Configuration\Administrative Templates\System\Internet Communication Management\Turn off Automatic Root Certificates Update was Enabled, meaning that the OS wouldn't pull root CAs from Microsoft. Setting this to Disabled fixed the issue.