http://docs.redhat.com/docs/en-US/Red_Hat_Network_Satellite/5.4/html/Installation_Guide/sect-Installation_Guide-Maintenance-Changing_the_Satellite_Hostname.html states that the command for changing a Satellite's hostname is "satellite-hostname-rename", from package "satellite-utils". Actually, it's "spacewalk-hostname-rename" and "spacewalk-utils".
Changed 5.5 version to reflect "spacewalk-hostname-rename" and "spacewalk-utils" on all instances where it was written as "satellite-hostname-rename" and "satellite-utils"
Fixed in Red_Hat_Network_Satellite-Installation_Guide-5.5-web-en-US-3-13.el6eng