I just discovered kdenlive and I'm amazed at how quick the learning curve is.
I had never used any video-editing software, and first heard about it on a Wednesday evening, apt-get installed 24 hours later, and finished my first 4-min video on the following Friday. Apart from watching 3 tutorials it was mostly done intuitively.

The video is a spoof of "Pat & Mat", old Czechoslovakian stop-motion TV shorts (http://en.wikipedia.org/wiki/Pat_%26_Mat). It uses about 20 video clips/stills, 10 audio clips (all from the original TV shows) and an image overlay. Everything was "strobed" 6 times (down to 5 frames/sec ?) to emulate the stop-motion effect, and I sometimes played with the speed as well.

See here: http://www.youtube.com/watch?v=DzPddeEn9ms&cc_load_policy=1

It made it to the finals of a Facebook "Like" contest, and would of course like more votes (until august 21.): http://www.helginn.net/iphone4/

Done very good. Especially as this is your first video. Looking forward to more videos from you ;)