Some new Platform as a Service providers: cloudfoundry.com and dotcloud.com
I am on vacation so I have not had much chance to try the beta invites I just received for cloudfoundry.com and dotcloud.com but both look promising as works in progress.
For now, Cloud Foundry is set up for Ruby Rack applications (like Rails and Sinatra) and Java Spring apps. They currently support MongoDB, MySQL and Redis. They will release the core software if you want to run a cloud on your own servers.
Dotcloud supports a wide range of platforms and data stores. Their roadmap shows what is available right now and what is planned.
Both beta programs are free for now. It will be interesting to see what the costs are.