I had a similar problem quite some time ago. I traced through the boot
scripts and found the /etc/sysconfig/network file to be the culprit.

1. Change to the superuser.
2. Change the /etc/sysconfig/network (assumeing Mandrake) file to
reflect the correct hostname information. This is the file that sets
things on startup.
3. Use the hostname command to change the hostname while the system is
running. No reboot required. Just make sure they match and everything
should be cool.

The syntax looks like this:

hostname my.hostname.com