"Host key verification failed", SSH only working when signed in as root user

I am trying to ssh/scp from one machine on my network to another. The problem is that when I execute an ssh/scp command (ssh user@ip_machine_2) it is only "working" when I am logged in to the root account on machine_1. When sending this command as root I am prompted for the user' password on machine_2 and then I can access the account/transfer a file without any issues. If I log into the user account on machine_1 and repeat the command I am now getting an error: "Host key verification failed." Does any one have any idea on what could be causing this when not logged into the root account? I checked the permissions for both ssh and scp and they seem fine, so I think the user account might be missing some permissions for something critical in the network stack in order for ssh to work under this account.