I found
this long-running thread at ASC, started in 2012,
continues through April of this year. Although it's geared toward iPhones, the basics of it mimic your problem and potential solution.
From a scan of it, there seems to be no one thing that cures the issue. Cures ranged from what you've already tried to --
Using a direct USB port, not a hub
Different cable
Deleting an App (anything new or updated since last back-up)
Disabling wireless on the device
Restore the device as new
Use encrypted back-up or not
Disabling firewall or other security software
etc,etc,etc....
As you can see, there's much to try and you're not alone with the problem. In my scan of that thread, I didn't see that anyone had tried a back-up after creating a new user on their Mac or PC. Probably won't help, but easy to try. Whereas you can't back-up to either iTunes or iCloud, I would think the corruption or conflict resides on your device or network.
Maybe someone else will chime in with an aha! solution before you ultimately track your issue down. Keep us posted.