10 minutes, wow. I've only experienced that with Windows instances (especially in eu-west) which I rarely use. Solaris instances are slower too but those are still considered beta.

I've been working on a development tool for EC2 for the past few months so I'm starting and shutting down instances almost every day. All of the Linux instances I've started have come up in less than a minute and usually around 30 seconds.

Keep in mind, if you're using a custom image or one that's been modified it could take longer depending on how large the image is (lots of preinstalled software) and what scripts are running on startup.

You hit the nail on the head - most of my instances are windows because I'm using them to run a small piece of windows software on demand. Didn't know there was a difference. Here's hoping they get a bit quicker as time goes by (maybe there's just not a large enough pool of them yet).