I believe this comes as a shock to most people the first time they receive this email, it was to us at least. When we signed up with amazon there was no guideline or advice saying "hey in a year or 2 your hardware might fail or need replaced, have a migration plan ready"
Perhaps it was our naivety, but we just thought hey, its the cloud, what could go wrong?! Now of course are are battle hardened
[1] http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/instance-... (bottom of the page)
The last place I worked has a policy of making zero changes in production Friday-Sunday or around holidays. It was one of their better practices.
But "cloud" compute services should in general be treated as less reliable per individual unit unless your provider explicitly explain to you why not (such as guaranteeing to use a high-availability distributed filesystem), as you no direct way of ascertaining status of the underlying hardware. You need to plan for failure regardless.
Have you given any thought to moving to something like https://circleci.com? [disclosure: I work there]
But obviously if there's a hard failure, they aren't always going to be able to give you the amount of time you'd want. Generally speaking, you should have accounted for this situation ahead of time in your engineering plans. Amazon EC2 doesn't have anything like vmotion, it's just a bunch of KVM virts.
If you're using the GUI, the first time you try a shutdown, it will do a normal request, but then if you go back and try it again while the first request is still pending, you should see the option for doing a hard restart. Try that and give it some time. Sometimes it takes an hour or two to get through. Otherwise, Amazon's tech support can help you.