When an ssh session starts, the public-keys are being sent over an insecure connection until the authentication process is established.. This allows a person to intercept an ssh session and place their own public key in the connection process. SSH is designed to warn the user if a public-key has changed from what exists in their known_host file. The warning that is given is quite noticeable and ssh will drop the connection if the public keys are different, but user's may still trust the certificate because they may think that their company has changed the server's public key. This kind of attack isn't difficult because the dsniff package mentioned earlier contains the tools to perform it. This attack is more commonly called a "man-in-the-middle attack" (The End of SSL and SSH).
A temporary and easy fix for this is to first teach the user's how to recognize the signs that the host key has changed and what to do to get the proper host(s) public key. Second, post the public key for the ssh server(s) on a website, ftp server, or distribute it some other way so that users have access to it at all times.