It sounds like it is trying to apply the label to a version of that file that already has that label. If you use tf label
, it will move the label if it can, so you're doing that the right way.
One thing to check is whether the version in the workspace is the version that you want to label. Otherwise, specify the versionspec (e.g. the following will label the latest version of the file regardless of what you currently have in your workspace):
tf label "$/MyProj/MyFile.cs" /version:T /server:http://tfs:8080
If you could post the tf label
command line you're using it might also help.
(edit: the tf command above would work for tfs 2005 and 2008. You'll need to specify the project collection instead of server for tfs 2010).