Up to now you could run any Linux distribution on Amazon EC2, but you could only run Amazon's 2.6.16 kernel. Well strictly speaking there are two kernels: a 126.96.36.199 kernel for the 32-bit instances and a 188.8.131.52 kernel for the 64-bit instances. But recently Red Hat announced support for RHEL5 on EC2, and today they made it available publicly. The kernel you get if you launch its paid AMI (machine image) is "Linux version 2.6.18-53.el5xen (email@example.com)." Long story short, Amazon now has the capability of running multiple kernels on the instances, but alas this is not yet available to mere mortals (i.e. non-Red Hat). But hopefully wider availability of new kernels isn't too far off. It's nice to see EC2 evolving steadily.
If you're interested in all the gory technical details, see my post on the Amazon forum.