MPEG compression will make the key pretty tough without some additional steps.
Can you post a screenshot?
Was your footage captured as interlaced footage? If so, you can separate fields in the footage interpretation dialog box without having to transcode it.
However, transcoding it to a losslessly compressed/uncompressed format is generally a good working practice anyway.
Have you tried adding a Matte Choker to Keylight? That's what I use to clean up the edges. Tweak the settings.
Have you tried alternate keyers like Primatte or DV Matte? also, if you cannot resort to other keyers, it may be worth exploring some de-blocking/ de-artifacting tools and techniques, e.g. using Magic Bullet Frames, Revision FX SmoothKit or the old-fashiend way in AE - extract the luminance, use it as an adjustment layer and feed it into Compound Blur (or any alternate method that does more or less the same...). also consider experimenting with the lighting. Maybe your contrast is simply too harsh, furthering the creation of unnecessary block artifacts. Try to use a more equally balanced lighting next time and correct the colors and contrast in post instead of shooting "true to nature". Of course a new camera would help in the matter in the long run... ;-)