Well, that wasn't an editing software program at all. It was completely done in After Effects, a compositing/CGI program.

However, I am assuming you have a PC. I have heard good things about Vegas, but don't know about it's HD compatability (do you really need HD - do you have an HD camera?). Premier is crap. Speed Razor is supposed to be getting better (though used to be crap, and I've had the president of the company on the phone and told him so. Insight is good, but hard to find in the US (and a little more expensive, or at least used to be). For a while Avid had a free DV download, but I think it is gone, still their low end editor will do everything most people need (unless trying to be in the biz) and is probably your best bet.

If you have a Mac, then Final Cut is great (though I don't like the audio editing).

Adam