Um dos recursos do sistema de autoridade de certificação é que as coisas mudam. As raízes expiram, novas raízes passam a existir, os certificados são revogados, as raízes vão à falência depois de compromissos. Um mecanismo de atualização realmente precisa estar pronto para lidar com essas mudanças.
Há uma terceira opção disponível, que é usar uma CA diferente que ofereça certificados 2K assinados com uma autoridade há cerca de 10 anos. Isso não é Verisign, mas pode ser alguém como Thawte.
Se isso não funcionar, você precisará de uma solução de mistura. Forneça um site de teste com o novo CA escolhido para validação dos clientes e ofereça bastante aviso de que o certificado será alterado e dividirá até 25% dos clientes. Crie o máximo de documentação de atualização que você possa imaginar e crie mais enquanto os clientes se deparam com problemas. Salientar que atualizar as informações da CA é algo que todos os sistemas precisam fazer de vez em quando, portanto documentar isso é uma coisa boa a longo prazo; é uma boa prática.