I emailed the advice to a coworker and he got it working! We are concerned about changing more than one machine to the same hostname, currently our only solution is allow one login per user at at time. There are only a handful of users who have notebooks AND desktops, we figured we could sort that out later.

Basically, we have a network management tool (DMI from compaq) that allows us to remotely administer client machines, but a lot of the hostnames were not descriptive enough for us to really use it (no one had paid much attention to hostnames because there was no reason to). It does not use netbios names (machine names).