Automatic Weights Different on one side than the other
This seems to related to the fact that you have multiple disconnected parts (meshes) inside a mesh object. It always gives Blender trouble to auto-weight multiple-part meshes.

Two solutions, as far as I can see it:


Separate each sub-object within the object (Edit mode - Select - Ctrl+P - By loose parts).  Then apply automating weighted-painted solution to each part separately. (Of course, before doing that, delete the armature modifier, weight painting, and the existing vertex groups on the original mesh)
Even easier - if your mesh is 100% symmetrical, simply delete half of it, apply the weight painting, THEN mirror. The mirror side will have the exact same w.p. as the other one. Of course, it will still retain the potential w.p. errors due to disconnected meshes, but at least both sides will be identical.