Changing the hostname on a RHEL box is fairly straightforward if you perform the following steps.
First change the HOSTNAME line in /etc/sysconfig/network
Then change the hostname in /etc/hosts
From here you can either reboot for the changes to take effect or do the following two steps.
Force the system to start using the hostname.
$ sudo /bin/hostname new_hostname
Get syslog to use the new hostname.
$ sudo /sbin/service syslog restart