I used Ulead VideoStudio a long time ago (maybe more than two years) and I just didn't like the interface. Was too clunky for my taste. Vegas looks nice and is fairly intuitive.
I think the best approach would be to download one-month trials and give them all a whirl? Do you have any specific requirements - like support for HDV, AVCHD, multi-camera support? Do you want to get professional results (like wedding videos, commercials, live musical events etc.) or are you just looking to get your fingers wet? What is your level of expertise? Budget? Do you need comprehensive DVD authoring capability?
I would say check out trial versions for both Vegas Movie Studio and Premiere Elements for starters.