Isso pode variar um pouco dependendo do seu registrador, do serviço de hospedagem e de quantos "aliases" você tem, mas aqui está uma resposta geral para suas perguntas. Você está certo de que os "aliases" (CNAMEs no DNS) precisariam ser alterados, possivelmente em registros A para cada um apontando para o IP existente. Você mudaria seu registro de domínio primário para o novo IP. No entanto, e corrija-me se estiver faltando alguma coisa na sua pergunta, se você tiver um grande número desses CNAMEs que apontarão para o mesmo local e quiser mantê-los iguais, crie um novo registro A (em seu IP existente) e aponte todos esses CNAMEs para isso.
A melhor maneira de lidar com isso depende de você precisar mover alguns dos seus subdomínios para novos endereços IP no futuro. Em caso afirmativo, convém reservar um tempo para movê-los para os registros A agora. No entanto, se você quiser mantê-los todos iguais devido ao design do que você está trabalhando, provavelmente você deve criar o novo registro A para apontar todos os CNAMEs para.