So I'm pretty convinced the issue was the way I wrote the CAA records. I think my DNS provider didn't need the double-quotes in there and it caused issues. Reason I say that is because after introducing the CAA records, I suddenly had the certificate renewal errors.
Then when using a DNS check tool and I looked up CAA records for Google and Mozilla and more, none of them had the double-quote in there, but mine did. So I am sure that was the issue, as everything worked fine again after I removed the double-quotes.
I suspect the double-quotes was being taken literally as a string and so letsencrypt.org is not the same as "letsencrypt.org" in the DNS CAA record. I was able to later find the logs I had seen in the early morning which shows the following which confirms my conclusion: CAA record for <domain> prevents issuance.
So for anyone who comes across this later, make sure you're not using double-quotes I guess. haha.