Video tutorials are a great way of learning how to use Blender. Apart from having someone actually giving you a cool demonstration, they're the best way of getting to appreciate the power of Blender. (You won't believe the number of times I've heard 'Oooh! I didn't know Blender could do *that*!' when I gave a demo ;-).
Two great sources for video tutorials are this thread on CGSociety.org and the tutorials list on BlenderArtist.org. Finally, there's also a small list on Blender.org but I think that it isn't very up to date anymore.
Pay some attention to the first message in the CGSociety thread; they describe a number of video codecs that you may require in order to play these tutorials.
Of course, if you know of a cool (video-) tutorial that I should list here, just let me know!