I just resolved the problem:
The registry value of nameserver1 was set to an external DNS address and not to the loop back address. So the UCS was not querying itself when looking for a KDC server! However the other machines in the domain were correctly querying the UCS, and the shell command was by default querying the loop back address.
nameserver1 = 127.0. 0.1 or to the address of another domain controller.