We are experiencing the same problem and have attempted the same fixes (except for changing nameservers). No luck here either.
As for Jeroen, the problem started this night with update #46. However, we have SELinux disabled, so this cannot be the problem for us.
A sample of our logs:
apr...