Steve,

Did you manually create an Exchange profile for the account that SQLServerAgent is using on the machine that is hosting SQL Server?

On the machine that is hosting SQL Server, login as ntadmin and create an exchange profile.

That's the only thing that I can think of.

-Mike