Yes, as you can see, the weights for that bone are not Red, but yellow. That's like a 0.5 weight. Blue is 0, vertices not affected by that bone will be blue. And Red is 1, the max weight, where they will be completely affected by the bone.
Also, there's nothing wrong with vertices being part of 2 groups... the problem is if they are part of groups that are too apart: The vertices of the knee can be part of both the thigh and leg. But, I'd recommend to keep them to a minimum... in the preview image it looked as though some vertices were part of both the hand and head for example.
And, I'd recommend NOT to use blender's automatic weights as they won't be 1.0 (Red) and may even be badly done. Doing them yourself gives you more control and makes them right. And with weight paint, it doesn't take too long.
And last, I don't like video tutorials P: but here's the one I had used to learn about weight paint:
http://wiki.blender.org/index.php/Doc:2.4/Tutorials/Animation/BSoD/Character_AnimationIt's pretty complete. Go to the middle, to the Rigging section