I've verified maverick and lucid euca2ools for this bug, by doing the following:

==== Maverick Euca2ools ====
- launch ami-a6f504cf, ssh
  us-east-1 ami-a6f504cf canonical ubuntu-maverick-10.10-i386-server-20101225
- sudo mkdir /mnt/creds && sudo chown ubuntu:ubuntu /mnt/creds
  . /mnt/creds # creds file set up to have necessary environment vars
- add proposed and install/upgrade package
  $ mirror=$(awk '$0 ~ /^deb / { print $2 ; exit(0); }' /etc/apt/sources.list)
  $ echo "deb ${mirror} $(lsb_release -sc)-proposed main universe multiverse" | sudo tee -a /etc/apt/sources.list
  $ sudo apt-get update
  $ apt-cache policy euca2ools
  euca2ools:
    Installed: 1.2-0ubuntu11
    Candidate: 1.2-0ubuntu11.1
    Version table:
       1.2-0ubuntu11.1 0
          500 http://us-east-1.ec2.archive.ubuntu.com/ubuntu/ maverick-proposed/main i386 Packages
   *** 1.2-0ubuntu11 0
          500 http://us-east-1.ec2.archive.ubuntu.com/ubuntu/ maverick/main i386 Packages
          100 /var/lib/dpkg/status
  $ sudo apt-get install euca2ools
- dest=/mnt/dest
- sudo rm -Rf "${dest}" && sudo mkdir -p "${dest}" && cd "${dest}"
- name=euca-ami-rebundle-$(lsb_release -sc)
- arch=$(uname -m) ; [ "${arch}" = "i686" ] && arch=i386
- sudo euca-bundle-vol \
   --cert "${EC2_CERT}" --privatekey "${EC2_PRIVATE_KEY}" \
   --user "${EC2_USER_ID}" \
   --destination /mnt/dest \
   --arch ${arch} \
   --prefix "${name}" \
   --size 2048
- verify that / and target have the same fs info:
 $ sudo blkid ${name}.img /dev/sda1
 euca-ami-rebundle-maverick.img: LABEL="uec-rootfs" UUID="7742f6ee-e492-4019-a70f-877c43562a7b" TYPE="ext4"
 /dev/sda1: LABEL="uec-rootfs" UUID="7742f6ee-e492-4019-a70f-877c43562a7b" TYPE="ext4"
- bundle/upload/register
  #due to bug 665667, we have to bundle the .img file with the ec2-ami-tools
  ## begin bug 665667 work around ##
  sudo apt-get install ec2-ami-tools
  sudo rm *.part.* *manifest.xml
  aki=$(wget -q http://169.254.169.254/latest/meta-data/kernel-id -O -)
  sudo ec2-bundle-image \
     --cert ${EC2_CERT} --privatekey ${EC2_PRIVATE_KEY} --user ${EC2_USER_ID} \
     --destination ${dest} \
     --image ${dest}/${name}.img \
     --kernel ${aki} --arch ${arch}
  ## end bug 665667 work around ##

  bucket=smoser-test
  $ euca-upload-bundle \
   --access-key ${EC2_ACCESS_KEY} --secret-key ${EC2_SECRET_KEY} \
   --bucket ${bucket} \
   --manifest ${name}.img.manifest.xml
  $ euca-register ${bucket}/${name}.img.manifest.xml
- run the new instance, and verify you can connect
  ec2-run-instances <new_ami>
  ssh ubuntu@....

==== Lucid Euca2ools ====
I followed the same process as with maverick above, with the following differences:
- launch ami-88f504e1, ssh connect
  us-east-1 ami-88f504e1 ubuntu-lucid-10.04-i386-server-20101228
- $ apt-cache  policy euca2ools
  euca2ools:
    Installed: 1.2-0ubuntu10
    Candidate: 1.2-0ubuntu10.1
    Version table:
       1.2-0ubuntu10.1 0
          500 http://us-east-1.ec2.archive.ubuntu.com/ubuntu/ lucid-proposed/main Packages
   *** 1.2-0ubuntu10 0
          500 http://us-east-1.ec2.archive.ubuntu.com/ubuntu/ lucid/main Packages
          100 /var/lib/dpkg/status
- $ sudo blkid ${name}.img /dev/sda1
  euca-ami-rebundle-lucid.img: LABEL="uec-rootfs" UUID="844b1f46-656d-4a2f-b1b6-5c0d9d110731" SEC_TYPE="ext2" TYPE="ext3"
  /dev/sda1: LABEL="uec-rootfs" UUID="844b1f46-656d-4a2f-b1b6-5c0d9d110731" TYPE="ext3"