We have been through this before, haven't we?
But this time you gave a hint, and I was able to reproduce the problem. If you have the database in AUTO_CLOSE that could indeed be the problem.
I created a database on a USB disk, and to spice it up, I had attached the USB disk to a virtual machine where I had SQL Server running. I set the database in AUTO_CLOSE, and I created a simple job to run a stored procedure. I scheduled it to run every 10 minutes. And indeed it fails with this The job failed. The Job was invoked by Schedule 9 (slisk). The last step to run was step 0 (no steps ran).
Apparently, Agent is a little impatient when making the connection for the job step, and gives up when there is a just a small delay. Or if just stops at the gate when the database is closed.
What I find irritating is that I can't find any diagnostics which points to the problem. This is why your previous thread just went on and on. Had Agent only reported this problem somewhere, we would have understood this a lot earlier.
I guess the reason job started failing when you changed the schedule is that the previous time slot, there were already users in the database, so that it was open. Or the system was less busy, so the database opened before Agent gave up.
I was too lazy to try a CmdExec job myself, but I would expect that to work, since SQLCMD by default waits for 15 seconds before giving up on the connection. If nothing else, you will get better error diagnostics.