New Win 8 machines - Can't access shares anymore [HELP]

Hello,

I recently bought new computers for the office, and all of them run Win 8 (basic edition). I had backup jobs running on all of them (Win 7) for 2 years with no problem. Now I've been trying to set up my new backup jobs for a couple of days to no avail. No matter how I share a folder on the Win 8 machines, I keep getting a "Error connecting to" message. My server is running Windows Server 2012, and the ReadyNas has absolutely no problem connecting to the shared folder to perform the backup. I'm at a loss here as of what to do because I just get a general error. This is what I've tried.

1. Enabled/disabled homegroup
2. Changed Workgroup to match ReadyNas Workgroup
3. Disabled firewall
4. Tried connecting by IP and Computer Name with and without admin user/pass
5. Shared folders with Total access (read/write) permission to: Everyone, Anonymous, Admin, etc.
6. Enabled network detection (with automatic config of devices in network)
7. Enabled shared use of files and printers
8. Enabled/Disabled Windows managing Homegroup connections
9. Enabled/disabled 128 bit encryption
10. Enabled/Disabled password protected sharing
11. Modified the registry HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Lsa\everyoneincludesanonymous from 0 value to 1. Which helped me last time to get backups to work on the Win7 machines.

Help me please, I'm about to throw the ReadyNas out the window!!!

Thank you!

Juan