Login interactively from the machine that isn't working, and enter 'who am i' the host value needs to be the same as what is in parenthesis in the last field, whether this is an ip address, hostname or FQN, if you have used the same value as this, then the issue is not with the name of the host.