I've isolated my subject and placed him on a layer of his own, and changed the background layer. Trouble is, now my subject looks like a piece of cardboard placed on top of a background.

I want to make him blend in nicely. I figure the problem is the antialiasing around his edges; right now he's too sharp. How should I perform this?

You could:
1. Feather the person which will usually result in a more gradual / smooth transition into the background
2. When you make a cut out of the person paste it onto a new layer above the background then immediately go Layer > Matting > and choose either Defringe or Remove Black Matte or Remove White Matte.

One of those will usually do the trick. If you have PS CS3 the new Refine Edge can speed things up for you a little.
Regards, Murray