You can change the hostname in the System Preferences of Lion (client):
Go to:
- System Preferences -> Sharing
- See "computer name" at the top, enter something other than what's there.
- If you click "Edit" underneath, you should get something like hostname.domain. I usually see: computername.local
When you use hostname, you should get the value given when you click "Edit", e.g computername.local
It could be that what's currently there is too long and/or contains an illegal character. While a bit old and refers to a specific case of binding to Active Directory, according to this:
Use computer names and passwords that are less than 16 characters in length, and which only contain alphanumeric (A–Z, a–z), numbers (0–9), - (dash) and/or _ (underscore) characters when binding with Directory Utility
I would try a new computer name in accordance with that those rules to see if it corrects the problem: alphanumeric (A–Z, a–z), numbers (0–9), - (dash) and/or _ (underscore)
I don't use spaces either.