Deinterlace? Most of that looks like semi-transparent leftovers from fields. It should be possible to selectively deinteralce the edges after the key and then clean them up. Take your existing key, duplicate it, erode/ choke the top layer, assign it as an inverted matte to the bottom layer. the remaining "stroke" can now be deinterlaced. Then do the same erosion thing with the original key's edges, add slight feathering to both constructs and stack them on top of each other. the cleaner deinterlaced edges would now replace the original ones...
Good tips. But in this case, I'm only working with 1080/30p footage.
It's hard to say looking at the picture because it has already been chroma keyed and the jpeg compression adds more artifacts, but it looks strangely similar to the 4:2:0 "pal progressive" chroma bug (which, as Mylenium said, looks like interlaced video -yet it appears on progressive footage).
Can you post an uncompressed, unkeyed frame? I'm wondering if it can be fixed with the free plugin from "Zap" Andersson, Chroma Switcheroo (windows only, found at http://www.lysator.liu.se/~zap/aeplugs/ ).
Regardless of the above, there's a lot of ringing in the belt, turning coring/sharpening down when shooting would help a lot with chroma keying.