I could be wrong, but I believe the working theory here is that if a lead sulfate battery becomes TOO discharged (or is discharged too many times, or it's been long since a recharge) excessive sulfate buildup renders the battery irreversibly unchargable. Lead sulfate is a poor conductor, and if there is too much of it, the crystals just won't dissolve into solution, allowing the battery to be recharged. (I.e., you've got to have SOME lead metal surface around to conduct the recharging current.) By placing a metal sulfate in the electrolyte solution and running a recharging current through the battery, you effectively electroplate the electrode surface with metal (in this case magnesium, which is widely available). This provides enough conductive surface to the electrode to facilitate the reverse electrochemical reaction and get the lead sulfate crystals to dissolve in solution, whereupon the battery can be recharged as normal.
Then you have to replace the magnesium sulfate with a normal acid electrolyte to facilitate the primary battery electrochemical reaction.
Anyway, that's the explanation I've read. I'm not sure how well it holds up to scrutiny. Thoughts?