When the EC2 plug in is trying to spin up an EC2 Ubuntu or Debian instance it tried to install java from a pre-packaged version from S3. However, it fails because that S3 bucket no longer exists.

Log from Jenkins:
Authenticating as root
Verifying that java exists
bash: java: command not found
Installing Java
http://s3.amazonaws.com/hudson-ci/jdk/linux-i586/java1.6.0_12.tgz?AWSAccessKeyId=AKIAIDJCUGKQHECDV2AA&Expires=1322665612&Signature=V%2FMhdT1O4hHzmMKSKaFdU%2BZ%2FVaM%3D:
2011-11-30 14:06:53 ERROR 404: Not Found.
Failed to download Java
Status Code: 404

XML response if you follow the link manually:
<?xml version="1.0" encoding="UTF-8"?>
<Error>
<Code>NoSuchBucket</Code>
<Message>The specified bucket does not exist</Message>
<BucketName>hudson-ci</BucketName>
<RequestId>6383DB7EC8FEB033</RequestId>
<HostId>[removed]</HostId>
</Error>