This was actually bad info (my mistake). The issue ended up lying in the backup. Restoring components had to be done one at a time and that is what officially caused the error.

Edited response on later findings: On top of verifying server IP, hostname, domain, and DNS servers, you'll get the same error ("Unable to restore the data - Cannot find the deployment type, Restore completed...") if you're restoring your backup from...