I made a version of the photo with the only changes being to remove the change in contrast on one side, and the substitution of a new background. I wanted to show how much that improves the image. I didn't do some of the feathering tricks which would improve the blending of the foreground and background. I'd first want to adjust the contrast and such of the foreground. BTW, I should mention BoltBait's Photo>Combined Photo Adjustments. It contains a number of adjustments to spiff up photos.
To erase around something in an image, I suggest first using a fairly large eraser -- say a radius of 10. Erase all the large curves. When you reach areas with sharp curves or angles, or small indentations, skip them. When done, go back with a small eraser size and take care of the tight areas. Remember to erase short strokes, letting up on the mouse button often. If you don't, when you make a mistake and erase something you didn't mean to, the Undo will undo all the good erasures along with the bad. (As often as I remind myself to do that, I always forget!)
Make sure you keep the original version around. Sometimes when you finish, you'll find you erased too far in on an edge. Just use the Lasso tool to cut the area from the original photo, and paste it as a new layer into the edited photo. (It will paste into the exact same location, as long as you haven't cropped the new version -- which you should not do!) Then merge down. You'll have a second opportunity to erase it correctly.
One additional comment. You might think it would be a good idea to use the Magic Wand in areas where the contrast is high between the foreground and background, I've seldom had good luck with that method. I almost always end up with a raggedy edge, and pixels erased that shouldn't have been.Perhaps it's just my technique, or lack there of.