Please have a look at the wikipage http://fedoraproject.org/wiki/FCNewInit/Initscripts and change your initscripts to comply with the LSB standard. Especially check the exit status and add a LSB Header. E.g. starting a service should return with 0, if the service is already running and stopping a stopped service should also return with 0. Also check, if your service has to be _on_ per default, and turn it off in the old chkconfig line, if not. Thank you.
I've fixed this in rawhide to the limits of my understanding. The existing documentation is terrible, and there's no list anywhere of what services we can depend on. Is it cron or crond? sendmail or mta or something else? Of course, crond and sendmail scripts don't have LSB-compliant initscripts so it's impossible to tell what they would have for "Provides:". I honestly don't think these tickets should have been filed until at least the basic system daemons had been fixed so we'd have something to look at.