I noticed the same behavior. Factory reset did not help.
No auto-start application works at startup (not even the alarm !)
If you check in developer options>Running services, you can see that the services of every startup apps are running but they are somehow inactive and not starting the front end applications (no notifications for example).
You need to start every single one manually at every startup/reboot.
Once you started them, they works without any problem and they don't get killed by Android.
All is good until you shutdown or reboot the phone. Then you have to restart all your startup apps again...
This is clearly a bug.
Temporary workaround : putting an active widget of the application apparently helps it to auto-start correctly.