Comment 13 for bug 634487

@DanielDaniel, Branden,
  The easiest work around is
a.) start the instance as m1.small or m1.large (depending on if you want i386 or x86_64).
b.) install java
c.) stop the instance (ec2-stop-instances or /sbin/halt from inside the instance)
d.) modify the instance to be t1.micro (ec2-modify-instance-attribute --instance-type t1.micro <instance_id>)
e.) ec2-start-instances

Doing that means you don't have to register a new AMI, and will only cost time setting it up and 1 hour of m1.small or m1.large.