A imagem estava ruim. Depois de recriá-lo com outra máquina, consegui fazer o upload para a AWS.
Eu segui todas as etapas na documentação da AWS ao pé da letra, mas estou recebendo "ERROR: imagem não encontrada" quando tento fazer o upload via CLI (estou no Mac OS X Mavericks no terminal). Eu exportei a VM do VMware Workstation e a salvei como um arquivo OVF. Aqui está o meu comando para o EC2 CLI:
ec2-import-instance /Users/CrimKid/AWS_EC2/ec2-api-tools-1.7.5.1/UbuntuAWS.ova -f OVA -t t2.medium -a x86_64 -b my-import -o crimkid -w (secret_key) -p Ubuntu_Server -O (access_key_ID) -W (Secret_Access_Key) --private-ip-address 192.168.1.26