I'll admit I am stumped on this one. If I were in your shoes, what I'd do is:
- Disable selinux altogether (to try to eliminate it as the cause) temporarily.
- Play around with adding the -x option to crond. You can do this in /etc/sysconfig/crond. It appears that may provide you with debug output.
Earlier in the thread I had said I wasn't aware of a crond option to make him chattier, but that was on a CentOS 4 box. (I just checked a CentOS 5 box a moment ago and discovered it.)