Wrong (or partially right) on two accounts :
1) There were debris right from the start, and STS-1 crew reported them. But the problem in foam application were so frequent, contrary to what you think to assume, that they were considered variance more than problem.
2) the CFC started to be replaced from around 1995 on. Replacing CFC-11, Nasa certified HCFC 141b for use in the Shuttle Program. The "green" HCFC is used in all the machine sprayed areas of the tank. For all the remaining hand-made areas, they indeed stick to CFC.
HCFC was first used for STS-79, in 1996, and then expanded with STS-86.
So debris have nothing, or little, to do with the "green" HCFC replacing the CFC. The thing is just that media and fans talked more and more about the debris problem, and it came more and more to the public's knowledge. Perhaps also, the top executives at NASA realised that there was a real issue here and they could not ignore it longer (though, as we saw with STS 127, nothing has really changed today, even with all the improvement they made).