I had this issue recently as well, however I was running the backup job from server A but the database being backed up was on server B to a file share on server C. When the agent on server A tells server B to run a backup t-sql command, its actually the service account that sql is running under on SERVER B that attempts to write the backup to server C.
Just remember, its the service account of the sql server performing the actual BACKUP DATABASE command is what needs privileges on the file system, not the agent.