I had a very similar issue to this a while back. I wound up having to delete all my jobs and recreate them from scratch. For starters, try this:
Stop the scheduler service
delete the SCHEDULER.SCH file (I assume you have it backed up.)
Restart the service
Open the Scheduler (it should be empty now)
Create 1 new job
Confirm it runs as scheduled
If this works, then just re-create all your other jobs. Tedious, I know, but hopefully it helps.
Thanks, I think I might have tried something similar to that but then imported my backed up scheduler.sch file. I'll give it another try.