Remember that Teflon is fluro-chlorocarbon. This type of molecule tends to be tightly bound
with a very even distribution of charge (dipole moment). The only way to rapidly dissociate/decompose this type of molecule is by either high energy radiation, like you would find in the upper atmosphere in the case of, say, freon being decomposed and rapidly reformed leading to destruction of the ozone layer, or by using a non-polar solvent and the right reactants. Wow! That was almost a run-on sentence. Anyway, teflon will resist a dye.
Dyes work by having semi-stable strongly charged, usually double bonded, moieties which react easily with carbon or nitrogen. That is why you can't dye steel. Iron will react to form a salt, but will then flake away without making a firmly bonded patina.
Plastic has a polymer backbone whcih remains unchanged provided the dye only reacts with side chains or reacts to bond in such a way that the backbone is unchanged, or that only a thin layer of molecules of the surface facing the air is changed. Is that a little clearer?