photoshop - How to change background and maintain realistic effect?

I have like 30 different photos to process like this, but I want to know key things to maintain realistic photo by changing it's background, or maybe just modify background so it would be more pleasing to eye.(If you know tutorial related to my problem, please do provide it to me)

Here is the photo:

Here is my step 2:

Here is background:

Here is the result:

As you can see, it isn't any close to realistic feel. I fooled around with levels, but all I got was this and still it doesn't feels right.

First try:

Second try:

Update

Different background:

Answer

1. 
   

   Perspective and settings - like Darkcat Studio said.

   
   



2. 
   

   Direction of the light - in the second background, the side of the tree branches facing the camera near the couple are in shadow while the couple is lit from the front - you have to choose a background that has the same light direction has the foreground picture.

   
   


3. 
   

   Quality of the light - hard light vs. soft light, this was one of the problems with the first background (but a pretty minor one compered to the perspective)

   
   


4. 
   

   Amount of light - you have to match the lighting of the background and foreground, in your example the couple has way more light on them than the tree just a few inches away (that doesn't mean the background and foreground has to have the same amount of light but you need a realistic ratio)

   
   


5. 
   
   

   Color of the light - your background has a very "cold" blue light while the couple looks "warm" with a lot of red tones - if you have the raw files you can just change the color temperature, if not you can use RGB curves, to warm the photo bump the red channel up a little bit and the channel blue down, to cool do the opposite (but you can only change the color by a tiny amount before they start looking weird, especially with skin tones)

   
   

The funny thing is that those also "work" if you don't change the background - one of my favorite photos is a picture of my son in front of storm clouds where I exposed for the sky and used a flash to light my son - I have the completely unedited jpeg out of the camera and it looks as fake as your switched background pictures (really, no one believes me this is unedited) because the setting is unusual (when was the last time you've seen a person in front of storm clouds) my son is lit by hard light from the side on an overcast day (where there should have been soft light from above) the light difference between foreground and background isn't natural and the white balance of the flash and overcast sky doesn't match.