I wonder why they weren't using Public-Private crypto in the first place?

Perhaps because it would use up more space in the ROM? If so, I wonder what functionality they dropped from the ROM to add it now? I somehow doubt they made the ROM bigger - that would be very expensive at this stage of the chips lifecycle.