My first piece of advice to vim n00bs is simple. Use vimtutor until you can cruise through the entire thing without reference. When I was learning vim I would go as far as I could doing the exercises. If I forgot something I would start all over again from the beginning. Do this over the course of a week and you will begin learning quickly. My second piece of advice is to use vim for everything.
I was a vim user for whole years before I got around to running vimtutor. I was pretty amazed at how much I learned. The funny thing is that I knew of the command from the start and happened to be looking for ways to kill time while I was stuck on a plane with no internet access. Hmm, maybe I should disconnect more often...
I came across this on HN - http://vimcasts.org/
There was a HN discussion on this a while back - http://news.ycombinator.com/item?id=1297221 (Check the comments for resources that other HN'ers mention)
Hope this helps.