I managed to fix it. I'm not entirely sure what the fix was because I made too many changes at once.
I think it was an issue where SELinux suddenly didn't like Network Manager touching that file for some reason. No idea why that would suddenly be an issue.
Anyways, the four main changes I did:
First
# Cleared the contents of:
/etc/resolv.conf
Second
ausearch -c 'dnsmasq' --raw | audit2allow -M my-dnsmasq
semodule -X 300 -i my-dnsmasq.pp
Third
ausearch -c 'NetworkManager' --raw | audit2allow -M my-NetworkManager
semodule -X 300 -i my-NetworkManager.pp
Fourth
reboot now