When you are painting your weights on to the model you are changing the influence of the joint on that part of the model. Depending on what your ‘max influence’ was set at the time of binding you could end up just moving the weight back and forth from one joint to another.
I’ve had many problems with this myself and found that this way works best for me.
When binding the geometry set the max influence to 1.
Hold all of the weights, and then change the influences to 5 (for a nice smooth falloffs) SKIN – EDIT SMOOTH SKIN – SET MAX INFLUENCES
If you are still having problems and not sure what joint is controlling an area of your model then open the component editor.
WINDOW – GENERAL EDITORS – COMPONENT EDITOR
Select a vertex and under the ‘smooth skins’ tab you can see each joint and its controlling value over that vertex. Here you can manually change the value.

If you have any further problems I’ll be happy to try and help

Thanks
Pete