Você precisa substituí-lo em seu servidor de DNS principal. Se esse servidor é hospedado pela Limelight, então é aí que você precisa alterá-lo. Se o seu domínio foi transferido para o seu novo registrador e o servidor dele agora é o principal do seu domínio, é aí que você precisa alterá-lo.
EDITAR
Para responder à pergunta na sua edição, sim. Se os registros do NS apontarem para os servidores controlados pelo MediaTemple e não para os servidores do YahooDomains, o registro CNAME no YahooDomains será essencialmente inútil. Você precisaria adicionar o CNAME ao servidor no MediaTemple.