Certificate error when trying to use Software Update Server

I'm going to assume this is a network configured in one of the three private address ranges and using network address translation at the edge of your network. If so, have you set up local DNS services on your local network? If you haven't, then you'll want start there. I wouldn't expect to see a .local domain name used for software update services, or most other server-oriented activities. The .local top-level domain is reserved for what's variously called multicast DNS or mDNS or Bonjour or ZeroConf. That's commonly used for performing network name lookups, and particularly when there's no server and no DNS server present.

OS X Server really wants working DNS, and that's not .local for this use. That DNS might be served from a Windows Server, or from the OS X Server itself, or some other DNS server on the local network. Remote and public and ISP DNS will not work when a NAT'd network and a private address space is in use — the public or ISP DNS will not return translations for local (private) networks.

Making this more complex, more than a few Windows Server configurations have been misconfigured to use .local as the top-level domain, and that tends to cause problems as systems are supposed to query the mDNS and not the DNS services, which means your queries might not work the way you expect.

If DNS isn't right, the rest of the stack will have problems — that includes Software Update Services, as well as certificates. Certificates are dependent on having functioning DNS services.

To verify your local DNS configuration, launch Terminal.app from Applications > Utilities and issue the following harmless diagnostic command:

sudo changeip -checkhostname

You'll have to enter an administrative password for the sudo, might then see a one-time message about the use of sudo, and will then usually see some network details, and an indication that no changes are required, or that there are network or DNS errors.