Paint weights works on the vertices of the model. If you're painting inside the polygons or on the edges, you may not get the results you're looking for. Try painting on the vertices and see what happens. Also, check the VALUE of the brush is set to 1 and the MIN/MAX VALUES are set to 0 and 1 respectively. Check the radius of your brush. Do you see a red circle or a red circle with an X in it? If you see the X that means you cannot paint on the mesh. You'll have to make the mesh paintable first before you can paint on it. Also, did you bind the skin first? Make sure you have bound the skin to the skeleton before painting weights. (to be honest, I dont think you can paint weights to an unbound mesh... can you?) Anyway. Try those tips, and if it still wont works, reply back.