Embora seja difícil dizer sem mais detalhes, suspeito que esteja relacionado a um atraso na anexação dos volumes à sua instância durante a inicialização. Veja esta postagem no fórum para obter mais detalhes, mas eu acho que você pode querer adicionar alguma espera em seu UserData
script, como:
# Wait for the EBS volume to show up
while [ ! -e /dev/sdh ]; do echo Waiting for EBS volume to attach; sleep 5; done