Getting a complicated project from SD to HD is NOT and easy task, unless you cheat and get a plugin, but if you choose to go that route you will definitely encounter a degradation in picture quality.
The solution?
Start from square one. You have half the work already done (keyframes, efx, etc). Just size up your main comp to 1920 x 1080 and get crackin!
No easy way out, but at least you get to bill the client for it.
Joey