First, make sure it’s not your clock:
It was the clock. The NTP server was down, the system clock wasn’t set properly, I didn’t notice or think to check initially, and the incorrect time was causing verification to fail.
Otherwise, try this Ubuntu thing:
https://stackoverflow.com/questions/35821245/github-server-certificate-verification-failed