have you checked in component editor?
make sure your vertices are matched to the corresponding joint. sometimes you can just select then and set them to 1 <which equals 100% attached to that particular join> then paint freely.
This should be done before painting, I learned the hard way >.<
I would explain more, but am omw to class.
let me know how goes.