Trying to setup Windows Backup on a brand new install of Windows 7 Professional, I would encounter the error shown below: "The specified network location cannot be used" and details shows "This service cannot be started, either because it is disabled or because it has no enabled device associated with it. (0x80070422)
All the searches on the web kept pointing to authentication issues, or making sure all your Windows Services were running. I was using a known good set of credentials on the remote machine. I tried everything I could find, with no luck... until I stumbled upon the 'so obvious you missed it' answer.
All the weblinks talk about checking RPC service, Shadow copy stuff, etc... but they all failed to mention the most direct culprit - 'Windows Backup' which should be set to manual for proper operation.
You can get the error above if the Windows Backup windows service can not start. In my case it was set to disabled. Why is it set to disabled? I think in my case the Samsung Magician SSD software disabled it as part of it's optimization for SSD disks.
So if you hit the wall - check the obvious first.. Windows Backup service