I used Premeire for awhile and didn't ever really like the interface. I tried the other simple user friendly programs available from Microsoft's built in movie maker to Pinnacle to Ulead. I picked up Vegas 4 and I haven't looked back, and have since upgraded to Vegas 5. It gives me a very easy to use interface with tons of effects and the ability to work with seemingly endless video and audio tracks. Each track can be given a plugin chain (this allows me to set all scenes shot from one lighting situation on one track and color correct, saturate, contrast, etc) or I can set up a plugin chain per clip. And/or you can set an overall plugin chain for the whole movie (great for overcoming a camcorder shortfall like to correct a camcorder that has a tendancy to be slightly washed out, and soft you might set an overall plugin chain to sharpen +3, Brightness -2, and contrast to +3). Transitions are very simple, to dissolve all you do is overlap two clips and then you even have the option to set the falloff of clip A to the pickup of clip B. This just scratches the surface.
My 15m short utilized about 20 tracks of DV including audio tracks, and it is easy to get in and change something at any point in the film. The one thing that is still tough is if you change the length of a clip lets say at the 10m mark, you then have to move up the rest of the clips on the other tracks. This makes you plan out your edits very carefully because to go back and lop off part of a clip makes you have to go to every track and select events to end and slide them up.
When you get to that level it CAN get complicated, so I would say if you start doing complicated stuff like that, it is probably best to piece together scenes or sections at a time, render them, then go back and put them into the overall movie project as a clip.
Overall I would have to say that if you want to seriously get into filmmaking and want to learn how real pro NLE's work, Vegas will teach you this on the simplest to use level. I believe I have acheived expert status on Vegas after 8 months, 2 shorts and a re-edit of a feature (simple fixing of a few scenes and problems that were inherent of a feature made on SVHS 15 years ago), however now that I have really learned how to use the program, I am learning how to combine effects and complex edits into really flashy sharp looking productions.
Hope this helps, but as you said it is probably a great idea to download the demo of all the NLE's you have your eyes on. Some people love Premeire's interface. Some people love using Apple comps. I love using Vegas and PC's. Find what is right for you.