Hrmm is there an AlphaTransparency in the group that the label belongs to? If so, try commenting it out for a test. (You'll want that "a" flag there.)

Another thing I've had problems with before, was if I applied any kind of hueing/saturation to the overlay (doesn't look like you are, though).

You are using a newer version of xlabel, of course?