Spotlight can't see renamed label in Lion
It's a little convoluted, but I've found a workaround. The renamed label is still not appearing with the -label operator autocomplete, but you can search for it another way.


In a Finder window, choose File > Find
In the criterion dropdown (defaults to "Kind"), select Other... and enable File Label
Select the File Label criterion and all the colors will be available