Automatic weights don't seem to work properly on the mirrored side of my model
If your mesh is strictly symmetrical, there's one easy solution to this. Just delete one half, apply the weight-painting, then add the mirror modifier (and apply it, if needed). Now both halves are identical, weight painting included.