Are you suggesting that a few hundreds millions certificate shall be re-issued, distributed either in person, or per email, or even per post for some countries? Sounds easy :-)
Depends on how many certificates become invalid now.
Yeah, if half-smart, certificates should expire relatively frequently to contain damage in such a scenario.