Your client originally wanted smaller than web size and now they want 720 HD? Really? I hope you told that goofball that it would cost extra for that blunder.
Whatever you do, save your project with a different file name so if you royally screw up everything, you won't have lost your work.
You can try putting your comp in a 1280x720 comp and scaling it up with collapse transformations applied, but it may not look very good.
If not, you can go to composition>composition settings and make your comp larger. Then, create a null, parent all the layers to the null, and scale it up so everything fits...THAT might work.
Otherwise you can go to composition>composition settings and make your comp larger. Then go through each layer scaling it up and redoing some of the animation as needed. (This is the most expensive option, of course.)
When you say "keying" do you mean keyframing or do you mean layers with color key effects applied? If you meant keying, does the source footage that you're applying the chromakey effects on have 720 resolution or will you have to reshoot?
All that Michael said... This is slightly insane on the part of your client (not to say moronic). While some of the tricks with simply scaling and fitting may work, you will still find yourself rebuilding a considerable part. Especially the keying will need anotehr round of finetuning as the results may look notably worse on the full thing when they were just sufficient for the lo-res version...
The only right way to resize a composition is to use the Scale Composition script, then figure out which assets need to be redone to avoid scaling problems. You'll find the script under File>Scripts>Demo Palette (CS3 and later). It's easy to use.
Once you have your composition scaled up check everything to find out which assets (imported files) need to be recreated. I'd re-do any non vector (illustrator) art that has a scale value over 120%. If you have 3D layers check the distance to the camera. If the artwork is closer to the camera than the zoom value in pixels, that artwork will also need to be recreated.
Once you have the composition working, you'll need to check the speed and timing of all your animations to make sure that they will work with the new size and or frame rate. For a simple project, I'd charge at least another 2 hours for the rework. For a project like the one I just completed yesterday, it would me more like 8 hours. This kind of thing isn't easy to do right.