Agreed. Most providers appear to simply slap on the "Cloud" sticker to whatever VPS solution they were providing earlier with absolutely no change in features. These are the features that I believe should be present in any provider that claim themselves to be cloud providers:

1. Ability to scale up or down instances with change in demand.

2. Absolutely zero machine agnostic. I really should be bothered whether I am running a linux/windows/lego machine.

3. Auto configuration and notification - Leave little configuration to me so that I can concentrate more on the stuff I like. But, please do notify me in case the whole system burns down.

4. Easily available APIs that are globally used by all - a user account management, cache management, web UI framework etc.

If you see, there are only a few couple of sites (Google App Engine, Heroku et al.) that satisfy these conditions. Rest all are VPS wolfs on Cloud sheep suits.