TFS: TF30063: You are not authorized to access <server>

Problem:
When trying to work with TFS using the command line tool tf.exe on the TFS server, all commands end up with error: TF30063: You are not authorized to access <server>, <server> being the address of the TFS server you specified as tf.exe /server parameter, such as

C:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE>tf status /server:http:
//tfs01.mydomain.com:8080 /workspace:MyWorkspace /user:mydomain\myusername

Solution:
Instead of using DNS registered URL of the TFS server, use full computer name. So in my case command that worked was:

C:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE>tf status /server:http:
//ws000123.eu.mydomain.com:8080 /workspace:MyWorkspace /user:mydomain\myusername