So you say “widescreen” but do you mean HD? NTSC? Something else? If it’s just a 16×9 output you’re looking for you can build a custom project size in CS4 to fit whatever specs you need or decide you want. I used to edit all sorts of things at 640×360 for web delivery as an example. Not a standard broadcast spec but it is “widescreen” or 16×9.
In CS4 I think the option for building a truly custom resolution was still listed as “Desktop” mode. Poke around the settings tab of any project preset and you’ll find the window/pull down that can give you all the options you need. It changed in CS5 and I can’t cast my memory back there to where I can say for certain what the steps are.
If it’s truly a custom resolution that’s where you want to start. I’d say build it at 620×352 and see how the other clips look scaled up/down to fit it. Everything will need to be rendered, but that shouldn’t be too bad.