From the information above, something is blocking the communication.
Are you able to run this from the Protect console to the target?
net use \\machinename\IPC$
It may give you a better error to work off of.
Also, are you able to scan these machine when you manually add them to a new Machine Group? Maybe try NetBIOS, FQDN and IP in separate tests.
That was indeed the problem. An old version of our Checkpoint VPN client was causing the disconnect. The machines did not show it as present but found Processes running.
Glad to see you figured it out, thanks for taking the time to let us know!