DataNode cannot register with NameNode

[lfrancke]

We've seen one instance where a DataNode is not allowed to register with the NameNode.
We see this error in the logs:

Datanode denied communication with namenode because hostname cannot be resolved

And the NameNode logs:

Unresolved datanode registration

Setting dfs.namenode.datanode.registration.ip-hostname-check to false might help but we're not sure.
We have not been able to find the source for this issue yet.