Hostname issue in Mac OS X Lion
After a bit of playing about on the Terminal I've found a solution
sudo hostname <desired hostname>
this has permanently changed my hostname - I've tested it with a reboot and full shutdown and it seems to have done the trick! This doesn't explain why it gave me the odd hostname in the first place but that could just be because Lion is still new
The man page for 'hostname' says to use scutil to set it:
% scutil --set HostName "foo.domain.com"
This worked perfectly for me.