Also, what's the codec of the source material?
If it's a highly compressed one (DV, mid-quality MJPEG etc.) then you'll see this staircasing much more clearly when you've pulled your key than on your original unkeyed footage. There is a keyer designed for DV material, that works to smooth out these artefacts, but I can't remember exactly what it's called (DVmatte?).
You could also put a small blur on your matte.
Alternately, as it looks like a CG source, you could re-render your orignal footage to an uncompressed codec prior to doing any further work on it.
Hope that helps,
Ben
Curious Turtle Professional Video
Training | Editing |Support
http://www.curiousturtle.com
