Eu encontrei o problema. Foi bastante não intuitivo.
Quando o Active Directory é criado, a AWS cria automaticamente um grupo de segurança associado.
O SG foi chamado de "d-9462 ##### _ controllers" e tinha a descrição "AWS criou o grupo de segurança para os controladores de diretório d-9462 #####". (d-9462 ##### sendo o ID do diretório)
O que o torna contra-intuitivo é que este SG não é exibido em nenhum lugar (até onde eu sei) dentro do console dos Serviços de Diretório. Você teria que saber que ele existia e saber pesquisá-lo nos grupos de segurança da VPC.
Por padrão, o SG concede acesso somente ao VPC no qual o diretório reside.
Para corrigir o problema, você precisa conceder acesso explícito a qualquer outra VPC que precisar.