I had upgraded an older ESX 5.5 host for a customer to version 6.7. That night, when Veeam backup tried to run, it stated that the remote certificate was invalid.

The easy fix was to go to the Backup Infrastructure in Veeam and find the ESX host. Open the properties of the ESX host and "next" your way through the name and credentials pages. You will eventually get a pop-up about the untrusted certificate and asked if you "want to connect anyway". After accepting, the backups worked again.