Do you mean it hangs on request, not sometime later?
There are two options. One is that Amazon's call is just failing - I've seen stats that claim around 2% of all Amazon API requests fail for "no good reason" and you should always have a retry-on-fail kind of thing coded up.
The other is that you're doing something clever when your instance is starting and that's causing the actual linux OS to hang during its boot cycle. Like having added an init script to go insert some dynamic DNS or whatnot, or anything else relying on an external dependency that causes it to freak out. I'd move any custom stuff late in the boot process and maybe get some remote syslogging to see if there's something really going wrong at the OS level.
I'd tend to put my money on the former, however.