Como Michael afirmou nos comentários, o problema era permissões.
A única permissão necessária era 'kms: CreateGrant', que foi adicionado ao usuário do serviço usado para executar os comandos da CLI.
Minha equipe e eu recentemente passamos por um problema estranho em relação à AWS CLI. Estamos tentando usar a CLI para iniciar e parar várias instâncias do EC2. Ao testar comandos em instâncias únicas, notamos que é possível 'stop-instances' usando a CLI, mas não conseguimos 'start-instances' usando a CLI. Podemos iniciar instâncias sem qualquer problema no console da AWS.
Ao tentar iniciar a instância a partir da CLI, o estado muda de 'parado' para 'pendente', mas logo depois ele volta para 'parado'. O motivo desse estado é descrito como 'Client.InternalError: Erro do cliente ao iniciar'. As chaves de acesso usadas têm acesso para parar e iniciar a instância (Executar com opção de execução a seco mostra isso).
Alguma idéia?