I have to admit I have never seen that. I would generally point you at the share security and then the underlying file system security since that is usually the problem. But an entirely different user..

You said you restarted SQL and that SQL and agent are running as domain accounts. Do those domain accounts have rights on the share AND the filesystem? Any SQL Agent proxy account?

CEWII