Almost Identical scenario - Solution was to make sure the account being used by SQL Agent Service is a member of the SQL Server SysAdmin group. SQL Server service works fine - even though the account is not a member of teh SysAdmin group.
Background Info about Environment:
We recently created a new domain account that would be used to run SQL Server and SQL Agent services for a specific instance in a multi-instance, multi-CPU consolidated server(SQL2005 SP2). I added the domain account to the Local Admins group and opened up services.msc and modified teh logon account information. SQL Server service runs fine - but SQL Agent service would NOT startup.
Hope this helps somebody(or me the next time I make the same mistake)
Sudha