More info would help to diagnose the problem .... how did you bind your rig , is it smooth skin?
How are you selecting the paint weights tool (Skin > Edit Smooth Skin > Paint Skin Weights Tool) ?
Did you delete the history before binding the skin ( you need to have no history)?