Russell Brown's video shows this being done...
Also, sometimes, if you shoot an image with a radically different background than what you end up putting the subject in front of digitally, reflections in hair highlights and shading can make it seem unnatural. In those cases you really have no choice but to alter the subject subtly to make it "blend" better into the scene - e.g., with the Burn and Dodge tools.
People might make more specific suggestions if you'll put up an image (or even part of one) showing what you're working with.
Do you think that providing (a lores of) the image and the intended background might enable people to provide more specific advice?
How are you isolating/cutting out the subject? You'd want something that would feather the edges of it.
Also, a plain color background looks "too perfect". It can help to add some noise or a gradient.