A resposta foi muito simples. O arquivo de certificado não foi gerado pelo arquivo CSR, foi gerado por um arquivo CSR diferente. Eu simplesmente recebi um novo certificado e funcionou.
Após o certificado ser importado para o keystore, eu poderia executar o seguinte comando para assinar o arquivo intermediário do Adobe Air.
adt -sign -alias codesigncert -storetype jks -keystore codesignstore -storepass storepass123 -keypass password123 "C:\myapp\widget.airi" "C:\myapp\widget.air"