I found the answer to this. Any user who is not sysadmin has to have access to the proxy granted explicitly.

To grant access proxy accounts for non-sysadmins

1.In Object Explorer, expand a server.

2.Expand SQL Server Agent.

3.Expand Proxies, expand the subsystem node for the proxy, right-click the proxy you wish to modify, and click Properties.

On the General page, you can change the proxy account name, credential, or the subsystem it uses. On the Principals page, you can add or remove logins or roles to grant or remove access to the proxy account.

http://msdn.microsoft.com/en-us/library/ms187890(v=sql.100).aspx