I am not an expert at Premiere, but have used it. Here is my, very limited advice:
a) Unlike alot of software, Adobe maintain a very good online help system. Perhaps Adobe Support
b) YouTube is packed with a collection of helpful and unhelpful videos. I tend to think that if a video tutorial lasts more than 3 mins, it is likely to be rubbish.
c) Some members of forums.creativecow.net produce 'tutorial' videos.
d) The Adobe GUI may look intimidating. I advise making a list of the terms it uses to describe the bits and pieces (e.g. Project, Sequence. Clip).
e) Get a sense of what all the different Windows offer; and consider which are the most useful (e.g. Project, Effects, Timeline, Effects Controls).
e) Premiere should be able to do anything that Movie Maker can do.
(Before doing this, you may wish to check, but I am not sure you are allowed to rip off those particular videos and use them for music videos.)