On one of my server install I was setting up my hostname (server1.example.com) and knew that my VPS had setup my VPS with different name (example.vps) than the name I was using to setup as my Hostname.
So I made sure that:
127.0.0.1 localhost.localdomain localhost
x.x.x.x server1.example.com server1
but after a restart
After some reading on Google I figured out that this is a Virtualization issue that resets the hostname to the name the Host set your VPS to – just ask you Host to change your VPS name to the same name you are trying to use as your hostname. If your host does not want to do this then you could always run a startup script to set your hostname on startup. (You might then have some RDNS problems)