I'm very new to the topic of weight painting, and have just parented several meshes to a rig.
It all works well, except for one issue at the shoes (the bone of one leg not only drags that leg, but also the other one).
I selected the bone, and then the object that I was having trouble with (opposite shoe), and, sure enough, there was some weight painting on the shoe. I changed the brush to subtract, and dragged all of the levels (weight, radius and strength) up to their maximum. I then tried to remove the weight paint, but it was not subtracted.
Strangely, adding my own weight paint and then trying to remove it works; it is only the auto-generated weight paint that will not go away.
Here's my file: http://www.mediafire.com/?s30kckfkhqx8ga4