In case it helps anyone.
According to http://msdn.microsoft.com/en-us/library/ms181439(v=vs.80).aspx (the vs2010 one does not mention this but it still applies):
Labels created within the graphical user interface are scoped to the root folder of the team project within which they are created. Labels created from the command line are scoped to the longest common path shared by the items specified in the label command.
Not sure why MS have chosen to do this, as you can right-click a branch / folder and select "Apply Label" which is kind of misleading.