I am getting the same error and cannot manage to get around it.
I have a job that simply imports data from an Informix Db using a ODBC connection string (I have also tried a simpler package, but am getting the same error).
The package runs fine when executed in SQL server BID and when executed manually.
I have created a proxy user and appropriate credentials however I still get the error >
The process could not be created for step 1 of job # (reason: A required privilege is not held by the client). The step failed.
The account in question is running as an uber-admin (literally every box is ticked), it is the dbo of the database I am trying to upload to and it has a role within the msdb database with appropriate permissions (it was also the creator of the package)
Looked through here > http://support.microsoft.com/kb/918760 without success.
EDIT - I have also tried executing the step with the job as the SQL agent service but I get the "The package execution failed. The step failed" error when you try execute a package as a different login to what the package was created under.
Any help would be much appreciated.