Craig, uneven heating can normally be worked around with conscientious tending. I don't think they re-did the oven because the pies were suffering, but because the uneven heat was most likely requiring more turns and the oven was noticeably falling apart. If anything, I think the re-do, with what appears to be a taller ceiling, could have played a role in the abysmal results you witnessed and not have been a mitigating factor.
In other words, part of what makes the pizza you had so horrible is the even, chain-like browning. The uneven heat in the pre-re-do might have produced something better, not worse.
Lombardi's is best known for it's history, but, prior to your visit, I had never heard anyone complain about it, so the odds of the pre-re-do pizza being worse then today's pizza are pretty slim.