Если у Вас меры защиты ключа Уполномоченного лица УЦ обеспечивают невозможность его компрометации прежним владельцем (а именно, снятие копии этого ключа) то перевыпускать не требуется. В противном случае - требуется.
К таким мерам могут относиться:
Вариант 1. Хранение ииспользование ключа в ПАКМ "Атликс-HSM"
Вариант 2: Ключевой контейнер был записан на токен, с признаком "неэкспортируемый", с ПИН-кодом к токену с длиной не менее 6 символов и не более 3 попыток ввода неправильного ПИН-кода и токен хранится с разграничением доступа к нему по лицам и времени.

Постараюсь объяснить на пальцах...
Меняется уполномоченное лицо УЦ. Он может быть ещё и руководителем УЦ или гендиректором или уборщиком. Это не важно. Я понял, что Вас интересует именно событие со сменой уполномоченного лица УЦ как владельца корневого сертификата УЦ.
Будем считать время Ч1 как время, когда ключевой носитель (ключ на токене, экспортируемый) передаётся от Иванова к Петрову и передача оформляется соответствующей записью в журнале или актом приёма-передачи.
Интервал времени от начала действия закрытого ключа уполномоченного лица УЦ Иванова до Ч1 - компрометации нет т.к. Иванов не заявлял о компрометации.
Ч1 - компрометации нет т.к. событие происходит при, как минимум одном свидетеле (Петрове).
Интервал времени от Ч1 до Ч2 - компрометации нет т.к. Петров не заявлял о компрометации. Но Петрова гложет червячёк сомнения. А вдруг Иванов сделал себе копию ключевого контейнера? А вдруг он его как-то использует в своих целях? У Петрова есть подозрение, что закрытый ключ уполномоченного лица УЦ мог быть скомпрометирован Ивановым. Наступило событие, описанное тут http://www.cryptopro.ru/....aspx?g=posts&t=3451 , которое порождает внеплановую смену.
Ч2 - время, когда Петров подал заявление о необходимости внеплановой смены ключей уполномоченного лица УЦ, владельцем которых ранее был Петров.

Таким образом, все сертификаты изготовленные в период с начала действия закрытого ключа уполномоченного лица УЦ Иванова до Ч1, не требуют каких либо действий со стороны УЦ. Их не надо аннулировать и заменять.
Все сертификаты, изготовленные в период с Ч1 до Ч2 , надо аннулировать и заменять. В интересах Петрова, что бы между Ч1 и Ч2 не было изготовлено сертификатов.

Так что, коллега Laroux, Ваша причина описана в топике http://www.cryptopro.ru/....aspx?g=posts&t=3451 .

1. По 63-ФЗ есть новая сущность - сертификат юрлица - обезличен и не связан конкретно ни с кем из людей.
2. В вашем случае достаточно издавать CRL от другой ключевой пары, но чтоб ничего не переделывать с тем же DN - почитайте RFC 5280 там прописана процедура перезда и особенности автора CRL.

А где в 63-ФЗ такое указано "однозначно говорит, что в таком случае все выданные квалифицированные сертификаты прекращают свое действие"?!?! Это неизвестная для меня новелла :-)