Chroma Key (or Green Screen Key) will turn green things transparent -- so you'll put the new background on a video track UNDER not OVERLAYED on your Chroma Keyed clip. But, from your description, it appears that you know that.
In order for your background to follow the keyed area as it moves, you'll need to keyframe its movement -- essentially animating its position and possibly its size to follow the keyed around around your video frame.
It's certainly possible, but it might take a lot of work if you've got a lot of movement in your keyed picture. And I don't know any shortcut that will make it easier.
Do you understand how to keyframe movement?
I want to say that I briefly watched a turorial on it on youtube maybe? If it doesn't take to long would you like to explain? But if it's too much to type then I have no problem looking for videos online. What would I type, "keyframe movement green screen"?
Well, yours is a rather unique situation, since you're combining two things -- a Key effect and a motion path.
I'd concentrate on creating the motion. A search on "keyframing" is likely to turn up countless tutorials, since it's used in many forms in Premiere Elements. But look at creating a "motion path" to get the basics. Or take a look at my free Steve's Tips PDF available at http://Muvipix.com. Just do a search on "Basic keyframing."
Finally, here's something to consider. What is the object you're trying to key into your video? If it's a simple square object, it may be easier to create it as a graphic and keyframe it's movements ON TOP OF rather than BEHIND your keyed video. This would save you the Chroma Keying altogether, and you could just focus on keeping your object over the green box. (You might even be able to use Premiere Element's 8's Motion Tracking tool and save yourself the manual keyframing. Though that Motion Tracking tool has its own challenges and it takes me a couple of pages to explain how to use it in my book.
It all depends on what effect exactly you're trying to create. But simple is always easier than complicated.