AWS Achieves PCI DSS 2.0 Validated Service Provider Status
aws.typepad.com
aws.typepad.com
What it doesn't help is the dual control and change control issues. I'd love to know how small startups deal with the dual control issue. Ultimately there's going to be a sysadmin somewhere who can read memory, and once that happens, it's single control. Though, not having access to the physical hardware on EC2 makes it a bit more secure from the sysadmin.
There is a simple and easy way to get into compliance without moving your host - use hosted payment pages. PayPal, Recurly, Braintree, and the other top-tier providers all have hosted payment pages.
Every startup I have been employed by or consulted for w/r/t payments either has a physical box or uses hosted payment pages.
I know of a bunch of startups that use a hosted page (e.g. Paypal, Google Checkout, authorize.net SIM, whatever), and a bunch of startups that host their main site in the cloud but have a physical server for accepting CCs, but I don't know of any that accept CCs directly on a VM. I'd be pretty surprised to hear about it.