Some new Platform as a Service providers: cloudfoundry.com and dotcloud.com
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.