This should help somewhat
There are a couple things you can do to get a better key.
First off, use a matte. Its kinda hard to explain, but first off you need to pull a B&W key. That is, youll want your actor to be completely black, and the rest to be completely white. Then when you have that, adjust the choker on the matte to expand the matte maybe 5-10 pixels. You will then use this matte and overlay it over your original (unkeyed) footage. What this is doing is providing a window to look through, you will need to change the composite mode. You should now have your matte on top, and your clip in the bottom, and the matte should be hiding everything except your actor and a small outlined strip of green around him.
Now use your keyer. This makes it easier because you are no longer trying to key out the entire blue screen with all its inpurities, you are simply trying to key the small green outline around your actor. This works better because you dont have to select such a huge range of blue, you can simply just key the shades of blue that are closest to your actor and not worry about the rest.
Often times you get bad keyes when you are tyring to key out all of the blue in the whole frame, because there are many shades that the computer is seeing. This way, your only focusin on that small blue or green band that is around your actor (thanks to the matte) and the computer only has the key out the shades that are coming through from the matte.
I tried to explain this the best I could, hope its clear. Maybe someone else can elaborate on it more and make it sound better. I can see it in my head but im not that good at explaining things, so this was my best shot.
Also, some others posted some good techniques, like shooting progressive (which should avoid stairstepping) or deinterlacing, also I have no idea how well premiers keyer works, I know FCP has a pretty good one that I use most of the time. Hope this helps and good luck in the future.
- Ryan