How come when using putty or cygwin(windows ssh clients), I am able to use my host name like this
ssh shane@freevo
it prompts me for a password, and then I can log in.

when I try to log into the machine from my bsd box(I think When I ran linux it acted the same way) with the same command I get this error.
I have always had to use ips, hostnames have never worked for me using *nixs. I guess I was surprised that hostnames worked with both cygwin and puttys ssh clients.

try adding the hostnames to your /etc/hosts file - there should be examples in the file of correct syntax.

I am pretty sure my /etc/hosts is set up correctly.

What mechanism is allowing my windows ssh clients to have no problem using hostnames.

It could be one several things. The /etc/hosts entries would definatalye resolve the issue. But of course if the IPs of the hosts oyu want to connect to change, you have to manually edit them again.

Do you have a router, runnign DHCP? If so what kind. - It could be performing UPnP type services for windows, not letting linux use it (very unlikely)

Are the Linux machines running samba? - Related to windows beign able to access through the WINS protocol, kind of like a second DNS.

Ok, so anyway, show us the /etc/hosts file, and how bout /etc/resolv.conf too. Might help us find some solutions.