I think you're on the right track. The error indicates the failure was during "secondary validation". What that phrase refers to is how the ACME server is doing Multi-Perspective Validation. In short, it not only tries to validate from the primary LE datacenter, but also from a number of other datacenters across the globe to protect against a local traffic/DNS spoofing attack. But since a provider like Google has DNS servers all over the globe, it takes a while for the changes you make to propagate everywhere. Here's a related thread:
In short, you may just need to wait a bit longer after publishing the record and before initiating the validation. The certbot Google DNS plugin has a --dns-google-propagation-seconds parameter that defaults to 60 seconds that you should be able to tweak.