You can create your own AMI however you need to use the Amazon-supplied kernels. The newest they provide is 2.6.21. I have a listing of the FC (Fedora Core) kernels that I use for CentOS instances. I'm pretty sure they work fine with Ubuntu as well.
You'll want to bake these into your AMI once you register it using ec2-register. They can be modified at the time you start an instance but I favour having the right AKI (kernel) and ARI (ramdisk) to start with. Adding support for the ephemeral disks is useful as well. You're paying for the extra storage with larger instances, you might as well use it. My magic incantation for ec2-register:
ec2-register --snapshot snap-12345678 -K pk-XXXXXXXXXXX.pem -C cert-XXXXXXXXXXX.pem \
--description "EBS CentOS 5.5 i386" --name "base-image-i386-4" --architecture i386 \
--root-device-name /dev/sda1 -b /dev/sdb=ephemeral0 -b /dev/sdc=ephemeral1 \
-b /dev/sdd=ephemeral2 -b /dev/sde=ephemeral3 --region us-east-1 \
--kernel aki-6eaa4907 --ramdisk ari-e7dc3c8e
You can change the region, snapshot ID, description, name, arch, etc.
Also, remember the kernels & ramdisks are region-specific. I can't remember where I got this list but I had trouble finding it. Hope it helps someone out.
2.6.21 kernels are available as: