So I ran across this issue a couple of months ago and forgot to blog about it for my reference and anyone else that runs across this problem. So here's the issue, I have an Apex class scheduled in production that runs another Apex class. I've made some changes to this second class and need to deploy it to production. Before you do that, for Force.com platform requires you to delete the scheduled job for that class since they are related.
No problem. So I deleted the scheduled class, pushed my new code to production (passes all tests! w00t!) and went back to schedule this class to run and saw this error:
I went and looked at the class and noticed that it was no longer valid:
So here's how you fix the issue so that the class can be scheduled. You have to simply have to make salesforce recompile the classes and then it will be available to schedule.