Just happened to run into this issue and SQL Agent Job history is misleading as BOL says

"Backing Up to a File on a Network Share

For SQL Server to access a remote disk file, the SQL Server service account must have access to the network share. This includes having the permissions needed for backup operations to write to the network share and for restore operations to read from it. The availability of network drives and permissions depends on the context is which SQL Server service is running..."

https://msdn.microsoft.com/en-ca/library/ms179313(v=sql.105).aspx