Forum Moderators: open
If it's not that, I don't know, because I only know about Linux servers!
Also what is the load like on your server at the time agent is trying to start? If the SQL Server is doing something that can tie it up and prevent it from responding to queries (like rebuilding indexes or pulling down replicated data) SQL Agent will time out waiting for the server to respond and will throw back a "can't connect to server" error of some sort.
If SQL is already running (and I mean running for a few minutes without being overloaded) what happens if you start agent manually or if it's running STOP it and start it back up?