Networking CRAP - why can't this be easier in 2013

Hello Tim:
My guess is that it is a permissions problem.
See if you can map a network drive from the problem machines to the share on the machine hosting your folder where you want your backups to reside.
When prompted for credentials make sure you prefix the username with the machine name of the machine hosting the share followed by a back slash and a user name on the host machine that has proper access to that shared folder and that username's password..
MachineName\Username like MyWindows8Machine\[email protected] (in the event of a LiveID or whatever)

NOTE: I remember in Windows 7, backing up to network locations required Windows 7 Pro or above (Home Premium wouldn't do it) that may also be the case with Windows 8 as well.

 

First.... double check and confirm that there are no duplicate host names on the network. Then:
On the problem machine(s) remove the mapped drive and then,
Control Panel -> Credential Manager -> Windows Credentials
Select the windows credentials that reference the host machine and remove them.
Try again.

 

OK since I am a little behind the curve with respect to Windows 8.1 and it seems (if I'm understanding correctly) that, that is the machine that is hosting your network share where you wish your backups to reside.... let's assume that the backup process on one end or the other is having some trouble resolving your microsoft ID from within the backup interface (since you don't seem to have any trouble accessing the share otherwise.
So...... on the Windows 8.1 machine hold the WinLogo Key and strike the "R" key and then type
lusrmgr.msc
and hit enter
In the left column right click the "users" container and choose New User
pick a name .... JohnSmith
pick a password...... [email protected]$$w0rd
untick user must change password and tick password never expires.
Click OK and close the New user dialog box.
Now double Click JohnSmith in the middle column
Select the "Member Of" tab
Click the Add button
Click the Advanced button
Click the Find Now button
Select "Administrators" and click OK and OK again
Now back under the Member Of tab select "Users" and the click the Remove button, leaving only "Administrators in the Member of Box.
Click OK
Now that we've created a new user / member of the local Administrators group on the Windows 8.1 machine, try using that for authentication credentials on the problem machines from within the BackUp interface.
Same deal
MyWindows8.1Machine\JohnSmith
[email protected]$$w0rd

NOTE: The only other thing I can think of is that the host volume must be formatted NTFS, in order to host system images, which I assume is the case already since you've apparently succeeded at least once already.
Or maybe there is something still buggy going on with Windows 8.1
It is still only a preview release so who knows.