I've encountered this erro message a few times. One of the reasons this occurs is that the server can't verify and account with a domain controller. This happens when a user has access to a server through group membership. SQL doesn't know all the individuals in a group and so has to go off and find out. If the service account doesn't have the correct permissions or you have multiple domains then this can occur.
However the situation I had this week was that this was failing and none of the above were true.
The reason was that "Agent XPs" were disabled. Agent XPs are the extended stored procedures SQL Agent uses in its day to day job. The account verification process is an extended stored proc. That meant that when SQL Agent tried to verify a user it couldn't.
Annoyingly the error about "Agent XPs" didn't appear in the log for the job history but appeared in the SQL Agent error log. Mainy people don't know there is such a thing. Well there is. Since 2005 its easier to find but many still don't look there. This is a completely different log to that of the main SQL Server service.
I thought I could get around this by using a SQL account, but no luck. It still uses the extended stored proc.
So if you are running SQL Agent then you need to enable the "Agent XPs" using, the following. BOL states that this is done for you if you start SQL Agent through management studio. That could be a new feature in SQL 2008.
Note: If you have advanced options turned on then you don't have to turn it on again.
exec sp_configure 'advanced options', 1
exec sp_configure 'Agent xps', 0
exec sp_configure 'advanced options', 0