On the machine where it does not work, you are probably running the SQL Agent as a user which is not the default "Local System Account", and on the machine where it DOES work, you are running Agent as local system, right?

I just fixed this by going back to local system for Agent and running steps with proxies when needed. It seems like the domain service account we used for running Agent is not allowed to impersonate the proxy, but the local system account is.

Probably also solvable by allowing the domain service account to delegate.