Long time ago now and can't remember what solved it!

Make sure that your SQL Server Agent account has access to the drive the backup is held on. Try this.