I found all of my ubuntu 10.04 rightscale hosts had the same ssh key. The base image they use has one ssh host key that is never regenerated on instance creation, so effectively 100% of hosts are likely to have the same key for each system image.

RightScale has been notified and they are working on  notification and fixes for customers.

The script in this gist will regenerate your keys if you have the ones I know of (on the ubuntu 10.04 rightscale image)

AMI: ami-7c16e315