Ok, got this worked out.
With the assistance of Stephen (sorry, all I have of the name) from Symantec Technical Support we got this figured out.
It isn't the certificates on the register.brightmail.com site. They should be fixed, but they aren't the cause.
When Stephen said the problem is often firewalls, I didn't think so, but I went ahead and brought up the real time logs, and tried to register the Gateway again. Sure enough, a list of warnings that the packet was 1420 bytes and greater than the effective MTU of 1380.
The problem was the MTU on the WAN port of my Cisco ASA 5515. It was set to 1380, (someone was testing something, don't ask) I reset it to the default 1500, and attempted the registration again and, voila! the gateway is registered.
If you can't access your firewall or other appliance directly, get your network admin to watch the logs while you attempt to connect--you might find your problem.