Visibility is not related to the weather (cloudiness) but rather how clear the atmosphere is from particulates such as dust, pollutants, fog, salt and such. If there is little haze in your scene, you can set the visibility to upwards of 100km which should improve results for your blue and green bands which are often the bands that return negative reflectivity. You might also set the 2-band K-T to use the Over-water conditions which often provide better results in areas of higher humidity or water. There may still be negative values in some pixels after these changes. They are not uncommon over areas of water or shadow. These areas typically have low radiance and do not model well and should be masked for further analysis.