I figured I should post this information since a few of you are planning to nominate me this year.....
The very first time I've ever opened a video editing program to do anything was actually back in 1999 or 2000, when I attempted to make an opening sequence to put on my fansubs (Not AMV) when I fansubbed back in the day. I think that was Premeire 4.x or 5.x... don't remember. Anyway, that failed misserably, so I went with a still image ;p
Ordinary Day was my first real attempt at making anything in any video editing application, (done in premiere) and was completed early 2004. I was inspired to start making my own AMVs after seeing Kwasek's 1000 miles shown at... I think AWA it was... in 2003. Hence the stark similarity (being a ghibli movie and Vanessa carlton song) and I even used Kwasek's video as a model of what to do for edits in a video.
So its Kwasek's fault that it even came out anywhere near halfway descent, and that I kept making AMVs since then ;p