"I did restore msdb from a backup" - this could be your problem.

Check something has permissions to run xp_sql_agent_is_starting, and that the msdb & master databases have the same owner.