Eu descobri que o problema era que o cloud-init foi apressado para o F16 no último minuto. Como resultado, o cloud-init só funciona com a configuração cloud-config. Para fazer com que o fedora funcione com scripts de entrada de dados do usuário, decidi usar um Fedora 18 AMI, onde esta funcionalidade é incluída por padrão.