While in my company we are loving S3 since it's really cheap and good, we can't say the same for EC2: the small instances are too slow, and the bigger instances are too costly and still can't compare with a decent Linux box. Overall we made our math and to have our servers in the server farm is going to cost less compared to EC2. Of course it's not going to be as simple to manage as EC2 is, but it is an acceptable compromise for now.
I think that here there is space for new startups if they are able to provide better performances at the same cost. I wonder if a configuration where in a cloud real hardware is selected in order to run an instance could work, instead to use virtualization technologies. This does not allow to take advantage of the fact that most boxes are not under high load most of the time, but maybe could work if it will be possible to use very low energy in this condition.